[알고리즘] 알고리즘 예술 (2)

국민 총생산 은 몇 년 에 두 배가 됩 니까?
우리 나라 공업 과 농업 총생산액 이 매년 9% 의 속도 로 증가한다 고 가정 하면 몇 년 에 두 배로 늘 었 느 냐 고 물 었 다.
인 스 턴 스 분석:
두 배로 늘 어 나 는 것 은 원래 의 두 배로 변 하 는 것 을 의미 하 는데, 매년 9% 만 늘 어 나 는 것 은 매년 1.09 를 곱 하 는 것 과 같다.우 리 는 프로그램 에서 1.09 를 끊임없이 곱 하고 이에 대해 계산 할 수 있다. 만약 이미 두 배 에 이 르 렀 다 면 계수기 의 값 은 바로 거 쳐 야 할 연수 이다.
이것 은 사전에 순환 횟수 를 확정 할 수 없 는 순환 이다.

#include<stdio.h>
　　　int main()
　　　{int  n = 0;
　　　 float  y = 1;             //       1，     int
　　　 while( y < 2.0){         //     2         
　　　   y *= 1.09;
　　　   n++;                    //    1.09        
　　　 }
　　　 printf(“%d
”, n);
　　　 getch();
　　　 return 0;
　　　}　　　

이 프로그램 은 for 순환 으로 도 실 현 될 수 있 습 니 다.

#include<stdio.h>
　　　int main()
　　　{int  n;
　　　 float y = 1;
　　　 for(n = 0; y < 2.0; n++)    //             
　　　   y *= 1.09;
　　　printf(“%d
”, n);
　　　getch();
　　　 return 0;
　　　}

동전 을 바꾸다
1 원 짜 리 인민 폐 는 1 점, 2 점, 5 점 짜 리 동전 으로 바 꾸 는데 모두 몇 가지 방법 이 있 습 니까?
인 스 턴 스 분석:
이것 은 사실 제3 장 중의 한 예 이다. 여기 서 우 리 는 다른 문제 풀이 방향 을 제시한다.
1 원 을 모두 5 푼 짜 리 동전 으로 바 꾸 면 20 개 를 바 꿔 야 한다.모두 2 점 짜 리 동전 을 쓰 면 50 개 입 니 다.1 푼 짜 리 동전 을 모두 쓰 면 100 개다.
만약 에 우리 가 m 개 5 분 의, n 개 2 분 의 것 을 사용한다 면 이 두 변수의 수치 범 위 는 각각 0 < = m < = 20, 0 < = n < = 50 이다.
m 는 21 가지 수치 가 있 고 n 은 51 가지 수치 가 있다.
우 리 는 '5 분 의 개수' 를 대표 하 는 m 와 '2 분 의 개수' 를 대표 하 는 n 에 게 각각 범위 내 에서 하나의 값 을 취하 게 합 니 다. 만약 에 이 두 가지 동전 을 합치 면 100 점 (1 원) 을 초과 하면 이 m, n 의 조합 은 사용 할 수 없습니다. 합치 면 100 을 초과 하지 않 고 100 이 부족 한 부분 은 1 점 의 동전 으로 보충 할 수 있 습 니 다.따라서 이 조합 은 사용 가능 한 교환 방법 이 어야 한다.
m 와 n 으로 하여 금 가능 한 모든 조합 을 다 찾 게 하면 모두 얼마나 많은 교환 방법 이 있 는 지 알 수 있다.
코드 는 다음 과 같 습 니 다:

#include <stdio.h>
　　　int main()
　　　{int  n, m, k, count = 0;         //count    
　　　 for(m = 0; m <= 20; m++)
　　　   for(n = 0; n <= 50; n++)
　　　     if(m*5 + n*2 <= 100)
　　　        count++;
　　　 printf(“  %d    
”, count);
　　　 getch();
　　　 return 0;
　　　}

   또한 궁 거 법 을 사용 하지만 m 와 n 의 수치 만 궁 거 하기 때문에 이전 보다 순환 이 적 고 효율 이 높다.
이정표 상의 대칭 수
고 른 속도 로 달 리 는 자동차 한 대가 아침 에 운전 자 는 역정 비 에 있 는 숫자 가 대칭 수 라 는 것 을 보 았 다. 67576, 2 시간 후에 야 그 는 또 하나의 대칭 수 를 보 았 다. 자동차 속도 가 얼마 인지 물 었 다.
인 스 턴 스 분석:
자동차의 속 도 를 알 기 위해 서 는 두 번 째 대칭 수가 얼마 인지 알 아야 한다.우 리 는 다음 과 같은 방법 으로 두 번 째 대칭 수 를 찾 습 니 다. 67576 이후 의 모든 수 를 순환 으로 판단 하고 대칭 수 여 부 를 봅 니 다. 만약 그렇다면 순환 을 멈 추고 (break 로) 그렇지 않 으 면 다음 수의 판단 을 계속 합 니 다.
이것 도 사전에 순환 횟수 를 확정 할 수 없 는 순환 이다. 순환 조건 의 작성 방법 은 두 가지 가 있다.
(1) 순환 조건 을 1 로 쓰 거나 쓰 지 않 고 순환 체 에서 종료 조건 을 설정 합 니 다.
(2) 미리 변 수 를 표지 로 설정 합 니 다 (값 이 0 은 대칭 수 를 찾 지 못 한 것 을 의미 하고 1 은 찾 았 음 을 의미 합 니 다). 순환 조건 은 이 변수 가 0 과 같 습 니 다.
코드 는 다음 과 같 습 니 다:
방법 1:

#include<stdio.h>
　　　int main()
　　　{long  i;                       //  32767,    long
　　　 int  a,b,c,d,e;               //    5   
　　　 for(i = 67577;    ; i++){   //               
　　　   a = i%10;                    //      
　　　   b = i/10%10;                //      
　　　   d = i/1000%10;              //      
　　　   e = i/10000;                //       
　　　　if(a == e && b == d)       //          
　　　　   break;
　　　}
printf(“     ：%5.2f
”, (i-67576)/2.);  //  “2.”
getch();
　　　 return 0;
　　　}

방법 2:

#include<stdio.h>
　　　int main()
　　　{long  i;                       //  32767,    long
　　　 int  a,b,c,d,e;               //    5   
　　　 int  flag = 0;                //            
　　　 for(i = 67577; flag == 0; i++){   
　　　   a = i%10;                    //      
　　　   b = i/10%10;                //      
　　　   d = i/1000%10;              //      
　　　   e = i/10000;                //       
　　　　if(a == e && b == d)     //     
　　　　   flag = 1;
　　　}
　　　printf(“     ：%5.2f
”, (i-67576-1)/2.);
　　　getch();
　　　 return 0;
　　　}

   주의:
   방법 2 평균 속 도 를 계산 할 때 피 제 수 는 1 개 를 더 줄 여야 한다.
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
전전 할당 법 표현 식 값 구하 기
표현 식: 앞의 20 개의 합, 세 개의 소 수 를 유지 합 니 다.
인 스 턴 스 분석:
이 표현 식 은 두 가지 특징 이 있 습 니 다.
(1) 두 번 째 항목 부터 모든 분 자 는 앞의 분모 와 같 고 분 모 는 앞의 분자 분모 의 합 과 같다.
(2) 플러스 와 마이너스, 플러스 와 마이너스 가 교차 합 니 다.
첫 번 째 특징 에 대해 우 리 는 앞에서 소개 한 반전 할당 방법 을 사용한다.이 프로그램 은 순환 으로 화 해 를 구 해 야 합 니 다. 우 리 는 변수 a, b 로 첫 번 째 분자 분 모 를 표시 하고 a / b 로 첫 번 째 값 을 계산 한 다음 에 b = a + b 로 다음 항목 의 분 모 를 계산 한 다음 에 a = b - a 로 이전 항목 의 분 모 를 다음 분자 로 만 든 다음 순환 에 들 어가 다음 항목 의 값 을 계산 해 야 합 니 다.
두 번 째 특징 에 대해 우 리 는 변수 sign = 1 을 설정 할 수 있 습 니 다. 매번 순환 할 때마다 sign 에 - 1 을 곱 할 수 있 습 니 다. 그러면 a / b * sign 은 sum 에 합 쳐 야 하 는 값 입 니 다. 그 기 호 는 바로 플러스 와 마이너스 입 니 다.   

int main()
　　　d{float sum = 0;
　　　int  a = 1, b = 1, sign = 1, i ;
　　　 for(i = 1; i <= 20; i++){
　　　   sum += ((float)a/b) * sign;
　　　   b = a + b;                   //        
　　　   a = b - a;                   //        
　　　   sign *= -1;                  // sign  
　　　 }
　　　 printf(“%5.3f
”, sum);
　　　 getch();
　　　 return 0;
　　　}

   주의:
   프로그램 에서 sum + = (float) a / b) * sign;한 줄 이 강제 유형 전환 을 하지 않 으 면 모든 결 과 는 0 이 고 최종 결과 도 0 이다.
난수 생 성
   200 명 이 있 습 니 다. 번 호 는 1 부터 200 까지 10 명 을 무 작위 로 뽑 아 상 을 받 았 습 니 다. 추첨 을 마 치 십시오.
인 스 턴 스 분석:
현실 생활 에 서 는 무 작위 추첨, 무 작위 시험지 생 성 등 몇 가지 수 를 무 작위 로 생 성 해 야 하 는 경우 가 많다.프로그램의 임 의 수 는 임 의 함수 로 생 성 되 어야 합 니 다. TC 에서 임 의 수 와 관련 된 함 수 는 rand (), srand (), random (), randomize () 가 있 습 니 다. 그들 은 모두 stdlib. h 에서 정 의 된 것 입 니 다. 그 원형 과 역할 은 다음 과 같 습 니 다.

int  rand();

역할: 랜 덤 수 를 생 성하 고 범위 0 ~ 32767.

void srand(unsigned seed);

역할: seed 로 피 드 를 만 들 고 난수 발생 기 를 초기 화 하 며 시스템 시간 에 피 드 를 만 듭 니 다.

srand(time(NULL))。
int random(int num);

역할: 랜 덤 수 생 성, 범위 0 ~ num - 1.

void randomize();

역할: 시스템 시간 으로 피 드 를 초기 화하 기 위해 서 는 time. h 헤더 파일 이 필요 합 니 다.
이 문 제 는 200 명 중 수상 자 를 뽑 아야 하 며, 뽑 은 번호 범 위 는 1 ~ 200 이 며, rand 나 random 함 수 를 사용 할 수 있 으 며, 아래 두 가지 방법 모두 1 ~ 200 칸 의 무 작위 수 를 생 성 할 수 있다.

rand()%200 + 1;
random(200) + 1;

이 예 는 뒤의 방법 을 채택 한다.
random (200) + 1 만 사용 하면;임 의 수 를 생 성 합 니 다. 프로그램 을 실행 할 때마다 생 성 된 수 는 같 습 니 다. (단, 한 번 실행 할 때 random () 을 여러 번 호출 하여 생 성 된 수 는 다 릅 니 다.)매번 실행 할 때마다 생 성 되 는 난수 가 다 르 려 면 먼저 난수 피 드 함 수 를 사용 해 야 합 니 다:

randomize();    //     time.h  

이 문 제 는 1 ~ 200 칸 번호 10 개 를 생 성하 고 10 회 순환 하면 된다.

int i, n[11];
randomize();
for(i = 1; i <= 10; i++)
{
　　  n[i] = random(200) + 1;
}

그러나 여기 서 문 제 는 생 성 된 10 개의 수가 중 복 될 수 있 는데 어떻게 해 야 중복 을 피 할 수 있 습 니까?
이러한 방법 을 사용 할 수 있 습 니 다. 순환 과정 에서 하나의 수 를 생 성 할 때마다 먼저 저장 한 다음 에 앞 에 존재 하 는 모든 수 와 비교 하고 같은 것 이 있 으 면 새로운 수 를 다시 생 성하 여 원래 의 수 를 덮어 서 앞의 수 와 중복 되 지 않 을 때 까지 합 니 다.

int i, j, n[11];
randomize();
for(i = 1; i <= 10; i++){
  n[i] = random(200) + 1;
  for(j = 1; j < i; j++)
     if(n[i] == n[j]){
        i--;    
        break;
     }
}

코드 에서 i - - 의 목적 은 i 를 1 로 줄 이 고 i + + 를 실행 한 후에 i 를 원래 값 으로 바 꾸 는 것 이다. 그러면 다음 순환 에서 생 성 된 무 작위 수 는 원래 의 수 n [i] 를 덮어 쓸 수 있다. 이것 이 바로 본 알고리즘 의 교묘 한 점 이다.
미관 을 위해 서 는 무 작위 수 를 어 릴 때 부터 크게 출력 하 는 것 이 좋 으 므 로 무 작위 수 를 생 성 한 후 에는 정렬 이 필요 하 다.
이 인 스 턴 스 의 전체 프로그램 은:

#include <stdio.h>
　　#include <stdlib.h>
　　#include <time.h>
　　int main()
　　{int i, j, n[11],k,t;
　　　randomize();
　　　for(i = 1; i <= 10; i++){
　　   n[i] = random(200) + 1;
　　   for(j = 1; j < i; j++)
　　     if(n[i] == n[j]){
　　       i--;    
　　       break;
　　     }
　　　}
　　　//          
　　　for(i = 1; i <= 9; i++){
　　　  k = i;
　　　  for(j = i+1; j <= 10; j++)
　　　    if(n[j] < n[k])
　　　       k = j;
　　　  t = n[i];
　　　  n[i] = n[k];
　　　  n[k] = t;
　　　}
　　　//      
　　　for(i = 1; i <= 10; i++)
　　　　printf(“%5d”, n[i]);
     printf(“
”);
     getch();
　　　return 0;
　　}