제 가 원 하 는 건 필수 3 포인트, 예 제 있 는 거.

제 가 원 하 는 건 필수 3 포인트, 예 제 있 는 거.

제1장 알고리즘 초보
1.1.1 알고리즘 의 개념
1. 알고리즘 개념:
수학 에 있어 서 현대 적 의미 에서 의 '알고리즘' 이란 컴퓨터 로 해결 할 수 있 는 특정한 문 제 는 절차 나 절차 이다. 이런 절차 나 절 차 는 반드시 명확 하고 효과 적 이 어야 하 며 한 정 된 단계 에서 완성 할 수 있다.
2. 알고리즘 특징:
(1) 유한 성: 하나의 알고리즘 은 절차 가 유한 하기 때문에 유한 한 작업 을 한 후에 멈 춰 야 한다. 무한 한 것 이 아니 라.
(2) 확정 성: 알고리즘 중의 모든 단 계 는 확정 적 이 고 효과 적 으로 집행 되 고 확 정 된 결 과 를 얻어 야 지 애매모호 해 서 는 안 된다.
(3) 순서 성과 정확성
(4) 유일한 것 이 아니다. 어떤 문 제 를 푸 는 해법 이 반드시 유일한 것 이 아니 라 한 문제 에 대해 서로 다른 알고리즘 을 가 질 수 있다.
(5) 보편성: 많은 구체 적 인 문 제 는 합 리 적 인 알고리즘 을 설계 하여 해결 할 수 있다. 예 를 들 어 암산, 계산기 계산 은 모두 유한 하고 미리 설 계 된 절 차 를 거 쳐 해결 해 야 한다.
1.1.2 프로그램의 구조
1. 절차 와 구조, 기본 개념:
(1) 프로그램 구성 의 개념: 절차 구조 도 는 절차 도 라 고도 부 르 는데 정 해진 도형, 지향 선 과 문자 설명 으로 정확 하고 직관 적 으로 알고리즘 을 나타 내 는 도형 이다.
하나의 프로그램 구조 도 는 다음 과 같은 몇 가지 부분 을 포함한다. 해당 하 는 작업 을 표시 하 는 프로그램 상자, 화살표 가 있 는 절차 선, 프로그램 상자 밖 에 필요 한 문자 설명 을 포함한다.
(2) 프로그램 틀 을 구성 하 는 도형 기호 와 그 역할
프로그램 상자 이름 기능
시작 과 끝 은 하나의 산법 의 시작 과 끝 을 나타 내 고 그 어떠한 절차 도 없어 서 는 안 된다.
입 출력 상 자 는 알고리즘 입 출력 정 보 를 표시 하고 알고리즘 에서 입력, 출력 이 필요 한 위치 에 사용 합 니 다.
처리 박스 할당, 계산, 알고리즘 에서 데 이 터 를 처리 하 는 데 필요 한 산식, 공식 등 은 각각 다른 데 이 터 를 처리 하 는 처리 박스 에 적 혀 있 습 니 다.
판단 상 자 는 특정한 조건 이 성립 되 는 지 여 부 를 판단 하고 성립 될 때 출구 에 '예' 또는 'Y' 를 표시 하 며 성립 되 지 않 을 때 '아니오' 또는 'N' 을 표시 한다.
이 부분 지식 을 배 울 때 각 도형 의 모양, 역할 과 사용 규칙 을 파악 하고 절차 와 구조 도 를 그 리 는 규칙 은 다음 과 같다.
1. 표준 적 인 도형 기호 사용.그리고 두 가지 결과 만 있다. 다른 하 나 는 여러 가지 판단 이 고 몇 가지 다른 결과 가 있다. 5. 도형 기호 에서 묘사 한 언어 는 매우 간결 하고 분명 해 야 한다.
(3) 、 산법 의 세 가지 기본 논리 구조: 순서 구조, 조건 구조, 순환 구조.
1. 순서 구조: 순서 구 조 는 가장 간단 한 알고리즘 구조 이 고 어구 와 어구 사이 에 틀 과 틀 사 이 는 위 에서 아래로 하 는 순서 에 따라 이 루어 진다. 이 는 여러 개의 순서 적 인 처리 절차 로 구성 되 는데 그 어떠한 알고리즘 도 없어 서 는 안 될 기본 적 인 산법 구조 이다.
순서 구 조 는 절차 구조 에서 나타 나 는 것 은 절차 선 으로 프로그램 을 위 에서 하 는 것 이다.
아래 에 연결 하여 순서대로 알고리즘 절 차 를 실행 합 니 다. 예 를 들 어 설명도 에서 A 상자 와 B 상자.
상 자 는 순서대로 실 행 됩 니 다. A 상자 에서 지정 한 동작 을 수행 한 후에 야 계속 집 니 다.
행 B 상자 에서 지정 한 동작 입 니 다.
2. 조건 구조:
조건 구 조 는 알고리즘 에서 조건 에 대한 판단 을 통 해
조건 부 성립 여부 에 따라 서로 다른 흐름 의 알고리즘 구 조 를 선택 하 다.
조건 P 의 성립 여부 에 따라 A 상자 또는 B 상 자 를 선택 합 니 다. P 조건 의 성립 여부 에 관 계 없 이 A 상자 또는 B 상자 중 하나 만 실행 할 수 있 습 니 다. A 상자 와 B 상 자 를 동시에 실행 할 수 없고 A 상자, B 상자 도 실행 하지 않 을 수 없습니다. 하나의 판단 구 조 는 여러 개의 판단 상자 가 있 습 니 다.
3. 순환 구조: 일부 알고리즘 에서 흔히 어 딘 가 에서 부터 일정한 조건 에 따라 특정한 처리 절 차 를 반복 적 으로 집행 하 는 상황 이 나타난다. 이것 이 바로 순환 구조 이 고 반복 적 으로 집행 하 는 처리 절 차 는 순환 체 이다. 분명 한 것 은 순환 구조 에 조건 구조 가 포함 되 어 있다. 순환 구 조 는 중복 구조 라 고도 부 르 고 순환 구 조 는 두 가지 로 세분 화 될 수 있다.
(1) 、 하 나 는 당 형 순환 구조 이다. 다음 왼쪽 그림 에서 보 듯 이 그의 기능 은 주어진 조건 P 가 성립 될 때 A 상자, A 상자 의 집행 이 끝 난 후에 조건 P 의 성립 여 부 를 판단 한다. 만약 에 아직도 성립 되 었 는 지 여 부 를 판단 하고 A 상 자 를 집행 한다. 이렇게 A 상 자 를 반복 해서 집행 한다. P 가 성립 되 지 않 을 때 까지 A 상 자 를 집행 하지 않 고 순환 구 조 를 떠난다.
(2) 、 다른 유형 은 순환 구조 까지 이다. 다음 오른쪽 그림 에서 보 듯 이 그 기능 은 먼저 실행 한 다음 에 주어진 조건 P 가 성립 되 었 는 지 판단 하고 P 가 성립 되 지 않 으 면 A 상 자 를 계속 집행 한다. 주어진 조건 P 가 성립 될 때 까지 A 상 자 를 집행 하지 않 고 순환 구 조 를 떠난다.
당 형 순환 구조 부터 형 순환 구조 까지
주의: 1 순환 구 조 는 특정한 조건 에서 순환 을 중지 하려 면 조건 구조 로 판단 해 야 합 니 다. 따라서 순환 구조 에는 조건 구 조 를 포함 하지만 '순환' 을 허용 하지 않 습 니 다. 2. 순환 구조 에 하나의 계수 변수 와 누적 변 수 를 가지 고 있 습 니 다. 계수 변 수 는 순환 횟수 를 기록 하 는 데 사 용 됩 니 다. 누적 변 수 는 수출 결과 에 사 용 됩 니 다. 계수 변수 와 누적 변 수 는 보통 동기 적 으로 실 행 됩 니 다.한 번 더, 한 번 더 계산 하 다.
1.2.1 입 출력 문 과 할당 문
1. 입력 문
(1) 입력 문의 일반 형식
(2) 입력 문 구 는 알고리즘 의 입력 정보 기능 을 실현 하 는 역할 을 합 니 다. (3) '제시 내용' 은 사용자 에 게 어떠한 정 보 를 입력 하 는 지 알려 줍 니 다. 변 수 는 프로그램 이 실 행 될 때 그 값 은 변 화 될 수 있 는 양 을 말 합 니 다. (4) 입력 문 구 는 입력 하 는 값 은 구체 적 인 상수 일 뿐 함수, 변수 또는 표현 식 이 아 닙 니 다. (5) 제시 내용 과 변 수 는 '구분' 을 사용 합 니 다.만약 에 여러 변 수 를 입력 하면 변수 와 변수 사이 에 쉼표 ',' 로 구분 합 니 다.
2. 출력 문
(1) 출력 문 일반 형식
(2) 출력 문 구 는 알고리즘 출력 결과 기능 을 실현 하 는 역할 을 합 니 다. (3) "제시 내용" 은 사용자 가 어떠한 정 보 를 입력 하 는 지 알려 줍 니 다. 표현 식 은 프로그램 이 출력 할 데 이 터 를 말 합 니 다. (4) 출력 문 구 는 상수, 변수 또는 표현 식 의 값 과 문 자 를 출력 할 수 있 습 니 다.
3. 할당 문
(1) 할당 문 일반 형식
(2) 할당 문 구 는 표현 식 이 대표 하 는 값 을 변수 에 부여 하 는 역할 을 합 니 다.오른쪽 표현 식 은 하나의 데이터, 상수 또는 산식 일 수 있 습 니 다. (5) 한 변 수 를 여러 번 할당 할 수 있 습 니 다.
주의: ① 할당 번 호 는 왼쪽 에 변수 이름 만 있 을 뿐 표현 식 이 아 닙 니 다. 예 를 들 어 2 = X 는 잘못된 것 입 니 다. ② 할당 번 호 는 좌우 로 바 꿀 수 없습니다. 예 를 들 어 "A = B", "B = A" 와 같은 의미 의 운행 결 과 는 다 릅 니 다. ③ 할당 문 구 를 이용 하여 대수 적 인 연산 을 할 수 없습니다. (예 를 들 어 화 간 · 인수 분해 · 방정식 풀이 등) ④ 할당 번호 "=" 는 수학 에서 의 등호 와 의미 가 다 릅 니 다.
1.2.2 조건문
1. 조건문 의 일반적인 격식 은 두 가지 가 있다. (1) IF - THEN - ELSE 문, (2) IF - THEN 문, 2. IF - THEN - ELSE 문
IF - THEN - ELSE 문장의 일반적인 격식 은 그림 1 이 고 해당 되 는 프로그램의 구조 도 는 그림 2 이다.
그림 1 도 2
분석: IF - THEN - ELSE 문장에서 '조건' 은 판단 의 조건 을 나타 내 고 '문 1' 은 조건 을 충족 시 킬 때 수행 하 는 조작 내용 을 나타 내 며 '문 2' 는 조건 에 부합 되 지 않 을 때 수행 하 는 조작 내용 을 나타 내 고, END IF 는 조건문 의 끝 을 나타 낸다.THEN 뒤의 문 구 를 실행 합 니 다. 1. 조건 이 맞지 않 으 면 ELSE 뒤의 문 구 를 집행 합 니 다. 2.
3. IF - THEN 문구
IF - THEN 문장의 일반적인 격식 은 그림 3 이 고 해당 되 는 프로그램의 구조 도 는 그림 4 이다.
주의: "조건" 은 판단 의 조건 을 표시 하고 "문" 은 조건 을 충족 시 킬 때 실행 하 는 작업 내용 을 표시 하 며 조건 이 충족 되 지 않 을 경우 프로그램 을 종료 합 니 다. END IF 는 조건문 의 끝 을 표시 합 니 다. 컴퓨터 가 실 행 될 때 는 우선 IF 이후 의 조건 을 판단 합 니 다. 조건 이 맞 으 면 THEN 뒤의 문 구 를 집 행 합 니 다. 조건 이 맞지 않 으 면 이 조건 문 구 를 직접 끝내 고 다른 문 구 를 집행 합 니 다.
1, 2, 3 순환 문
순환 구 조 는 순환 문 구 를 통 해 이 루어 진다. 프로그램의 구조 와 구조 에 대응 하 는 두 가지 순환 구조 이다. 일반적인 프로 그래 밍 언어 에서 도 해당 형 (WHILE 형) 과 도착 형 (UNTIL 형) 두 가지 문구 구조 가 있다. 즉, WHILE 어구 와 UNTIL 어구 이다.
1. WHILE 구문
(1) WHILE 문장의 일반적인 격식 은 대응 하 는 프로그램 구조 이다.
(2) 컴퓨터 가 WHILE 문 구 를 만 났 을 때 조건 의 진실 여 부 를 판단 하고 조건 이 맞 으 면 WHILE 와 WEND 의 순환 체 를 집행 한다. 그리고 상기 조건 이 맞 으 면 순환 체 를 다시 실행 한다. 이 과정 은 반복 적 으로 진행 된다. 이때 컴퓨터 는 순환 체 를 실행 하지 않 고 WEND 문 구 를 직접 건 너 뛰 게 된다.이 어 웬 디 이후 의 문 구 를 집행 한다. 따라서 당 형 순환 은 때로 '전 테스트 형' 순환 이 라 고도 부른다.
2. UNTIL 문장
(1) UNTIL 문장의 일반적인 격식 은 대응 하 는 프로그램 구조 이다.
(2) 형 순환 까지 는 '후 테스트 형' 순환 이 라 고도 한다. UNTIL 형 순환 구조 분석 을 통 해 컴퓨터 가 이 문 구 를 수행 할 때 한 번 순환 체 를 실행 한 다음 에 조건 에 대한 판단 을 한다. 만약 에 조건 이 만족 하지 않 으 면 순환 체 를 다시 집행 하고 조건 에 대한 판단 을 한다. 이 과정 은 반복 적 으로 진행 되 고 어느 조건 이 만족 할 때 까지 순환 체 를 하지 않 는 다.LOOP UNTIL 문 구 를 건 너 뛰 어 내 린 후 다른 문 구 를 실행 하 는 것 은 순환 체 를 실행 한 후 조건 판단 을 하 는 순환 문 입 니 다.
분석: 당 형 순환 과 ~ 형 순환 의 차이 점: (학생 들 이 먼저 토론 하고 요약 한다)
(1) 당 형 순환 은 먼저 판단 한 후에 집행 하고 형 순환 이 먼저 실 행 될 때 까지 판단 한다.
WHILE 문 구 는 조건 이 만 족 스 러 울 때 순환 체 를 실행 하고 UNTIL 문 구 는 조건 이 만 족 스 럽 지 않 을 때 순환 을 수행 합 니 다.
1.3.1 역 전 상 나눗셈 과 더욱 상 향 감 손 술
1. 역 전 상 나눗셈. 유클리드 알고리즘 이 라 고도 하 는데 역 전 상 나눗셈 으로 최대 공약수 의 절 차 는 다음 과 같다.
(1): 큰 수의 m 를 작은 수의 n 으로 나 누 어 하나의 상인 과 하나의 나머지 수 를 얻는다.순서대로 계산 하 다 = 0, 이때 얻 는 것 은 원 하 는 최대 공약수 이다.
2. 더욱 감소 하 는 기술
우리 나라 초기 에 도 가장 큰 공약수 문 제 를 구 하 는 알고리즘 이 있 었 는데 그것 이 바로 더욱 감소 술 이 었 다. 에서 더욱 감소 술 로 최대 공약수 를 구 하 는 절차 가 있 었 다. 반자 반, 반자 불가 반 자, 보조 분모 & # 8226; 자식 의 수 는 적 게 줄 이 고 많이 줄 이 며 더 감소 하 며 그 수 를 구 하 는 등 이 있 었 다.
번역: (1) 두 개의 정 수 를 임 의적 으로 제시 하고 이들 이 모두 짝수 인지 아 닌 지 판단 한다. 만약 에 2 로 간략 한다. 그렇지 않 으 면 두 번 째 단 계 를 집행 한다. (2): 비교적 크다.