알고리즘은
잘 정의된 계산 절차
– 일부 값 또는 값 집합을 입력으로 사용
– 일부 값 또는 값 집합을 출력으로 처리
특정 컴퓨팅 문제를 해결하는 도구
– 문제 설명은 원하는 입력/출력 관계를 지정합니다.
– 알고리즘은 이 관계가 달성되는 프로세스를 설명합니다.
데이터 구조
– 적절한 데이터 구조를 선택하는 것이 핵심 문제입니다.
– 다양한 데이터 구조의 강점과 한계를 이해하는 것이 중요합니다.
알고리즘을 개발하는 방법
(1) 문제를 이해한다
– 문제를 정확하게 정의
– 입력과 출력을 정확하게 지정
– 문제에 대한 가장 간단한 대표 예제 구성
– 모든 상황을 고려
(2) 당면한 문제에 대한 간단한 해결책을 제시하십시오.
– 프로그램은 언어 독립적입니다.
– 정확한 문제 진술은 계획에 영향을 미칩니다.
(3) 계획을 실행으로 전환
– 문제 표현(데이터 구조)이 구현에 영향을 미침
의사 코드
– 여러 면에서 C, Java, Python과 유사
– 알고리즘의 본질을 간결하게 전달할 수 있는 방법 제공
– Pseudocode는 정해진 형식이 없습니다.
명시적으로 문제를 관련 기본 단계로 분류하십시오.
알고리즘 예시
– 입력: 일련의 숫자 A=(a1, a2, … an) 및 값 v
– 출력: v==A(i)가 되는 인덱스 i 또는 v가 A에 나타나지 않으면 NIL
– 알고리즘
(1) LinSearch1(A,v)
p = 0;
i=1에서 n까지
A(i)==v이면 p=i;
반환 p;
(2) LinSearch2(A,v)
i=1;
그리고 i<=n && A(i)<>v do i++;
i <= n인 경우
그런 다음 나를 반환합니다.
그렇지 않으면 nil을 반환합니다.
고려해야 할 사항
1. 첫 번째는 일치하는 요소의 마지막 값을 사용하고 두 번째는 첫 번째 값을 결과로 사용합니다.
이는 모호한 문제 설명 때문입니다.
첫 번째 또는 마지막 색인?
2. 일반적으로 LinSearch2가 LinSearch1보다 더 효율적입니다.
후자는 항상 전체를 스캔하기 때문입니다.
3. 주어진 문제에 대한 해결책은 항상 하나 이상입니다.
연습문제
0과 n 사이의 모든 소수를 결정하는 프로그램을 작성하십시오.
힌트) 에라토스테네스의 체를 구현합니다.
에라토스테네스의 체
2에서 소수를 찾고자 하는 숫자까지의 간격에 있는 모든 숫자를 나열하십시오.
2는 소수이므로 결과 목록에 2를 씁니다.
자신을 제외한 모든 2의 배수를 지웁니다.
3은 나머지 숫자 중 소수이므로 결과 목록에 3을 씁니다.
자신을 제외한 3의 배수를 모두 지웁니다.
찾을 간격의 모든 소수를 남겨두고 위의 프로세스를 반복하십시오.
이때 체로 사용되는 소수는 전체 수 n의 제곱근보다 작아야 한다.
#include <stdio.h>
void find_primeNumber(int maxNumber) {
bool arr(maxNumber+1);
arr(0) = true;
arr(1) = true;
// 2부터 해당 숫자의 배수를 지워나간다
for(int i=2; i<=maxNumber; i++) {
if(arr(i)) continue; // 이미 지워진 수라면 건너뛴다
// 이미 지워진 게 아니라면 해당 숫자의 배수를 모두 true로 만든다
for(int j=2*i; j<=maxNumber; j+=i) {
arr(j) = true;
}
}
for(int i=2; i<=maxNumber; i++) {
if(!
arr(i)) printf("%d ", i);
}
}
int main(void) {
find_primeNumber(100); //100까지의 숫자 중 소수 출력
return 0;
}
단어장
대칭: 대칭