(알고리즘) 알고리즘이란?

알고리즘은

잘 정의된 계산 절차

– 일부 값 또는 값 집합을 입력으로 사용

– 일부 값 또는 값 집합을 출력으로 처리

특정 컴퓨팅 문제를 해결하는 도구

– 문제 설명은 원하는 입력/출력 관계를 지정합니다.

– 알고리즘은 이 관계가 달성되는 프로세스를 설명합니다.

데이터 구조

– 적절한 데이터 구조를 선택하는 것이 핵심 문제입니다.

– 다양한 데이터 구조의 강점과 한계를 이해하는 것이 중요합니다.

알고리즘을 개발하는 방법

(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; }

단어장

대칭: 대칭