반응형 [Public] 컴퓨터공학27 [알고리즘] 소수를 구하자 (소수#1) 2009. 05. 08 (金) 수학시간에 배운 소수(prime number)의 사전적인 의미는 1보다 큰 정수 p가 1과 p자신 이외의 양의 약수를 가지지 않을 때의 p를 소수라 정의합니다. 반대로 다른 숫자의 곱으로 이루어진 소수가 아닌 자연수를 합성수라 합니다. 참고로 1은 소수도 합성수도 아닙니다. 1. 자연수 n 의 소수 판단법 ① 1부터 n까지 반복해서 n의 약수인지 확인한다. ② 만약 새로운 약수를 찾으면 count 변수를 +1한다 ③ 모든 확인이 끝난 뒤 약수의 개수가 2이면 소수이고 그렇지 않으면 소수가 아니다 2. 소스 #include "stdafx.h" #include bool IsPrimeNumber(int n); int _tmain(int argc, _TCHAR* argv[]) { .. 2009. 5. 8. [알고리즘] 하노이의 탑 2009. 05. 06 (水) 883년 프랑스 수학자 루카스(Lucas. E.)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안해냈습니다. 전설에 따르면 천지 창조 시에 가장 가운데 작은 구멍이 뚫린 64개의 금으로 된 원판이 하노이의 한 사원에 보관되어 있었다고 합니다. 이들 원판은 어느 것도 크기가 같지 않으며 그림과 같이 작은 원판이 큰 원판 위에 오도록 포개어져, 세 개의 기둥가운데 한 개에 끼워져 있었다고 합니다. 이러한 모양이 탑과 비슷하다 하여 하노이탑(Hanoi Tower) 이라고 부릅니다 1. 하노이 탑 정의 - 원판을 세 번째로 모두 옮겨놓아야 한다. 이때도 작은 원판이 큰 원판 위에 있어야 한다. - 원판을 옮길 때는 반드시 한 번에 한 개씩 옮길 수 있고 두 번째 막대기를 이용할 .. 2009. 5. 6. [알고리즘] 유클리드 호제법 2009. 05. 04 (月) 유클리드(B.C. 365 ~ B.C.300)는 기하학의 아버지라고 불리는 유명한 고대 수학자 그 중 가장 유명한 것이 13권으로 구성된 기하학 원본 그 책은 그 선배인 피타고라스 플라톤 히포크라테스등의 연구한 여러 가지의 자료를 정선하고 거기에 자신의 창작을 가미하여 조직적인 교과서로 편찬한 것으로 수학사상 최고의 성전 이라 할 수 있음 1. 최대공약수(GCD : Greatest Common Divisor)란 - 정수 a, b의 약수 중에서 공통된 약수를 공약수라 하며 공약수중 가장 큰 수를 최대 공약수라고 한다. - 최대공약수를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 1. 정수 a의 약수로 구성된 집합 A를 구한다. 2. 정수 b의 약수로 구성된 집합 B를 구한.. 2009. 5. 4. 이전 1 2 3 4 5 다음 반응형
