[알고리즘] 알고리즘 의 예술 (3)

큐 브 진 인쇄
   하나의 홀수 단계 (n 단계 로 설정) 의 방진 은 1, 2, 3... n2 를 방진 에 채 워 각 줄, 각 열 데이터 의 합 을 같 게 합 니 다. 이런 방진 이 바로 마방 진 입 니 다.
인 스 턴 스 분석:
마방 진 을 작성 하 는 데 고정된 방법 이 있 습 니 다:
(1) 1 은 항상 첫 줄 의 중간 에 있다.
(2) 2 부터 다음 수 는 항상 위의 수의 오른쪽 위 에 있 는 빈 칸 안에 있 습 니 다. 예 를 들 어 5 는 4 의 오른쪽 위 에 있어 야 합 니 다.
(3) 오른쪽 위 에 표 의 오른쪽 경 계 를 초과 하면 숫자 는 첫 번 째 열 에 채 워 지고 줄 수 는 변 하지 않 는 다.그림 16 - 1 의 3 과 8 은 모두 이런 상황 이다.
   오른쪽 위 가 위의 경 계 를 넘 으 면 숫자 가 마지막 줄 에 채 워 지고 열 수 는 변 하지 않 습 니 다.그림 16 - 1 에서 2 와 9 는 모두 이런 상황 이다.
위의 규칙 에 따라 계 산 된 위치 에 이미 숫자 가 존재 한다 면 다음 수 는 위의 수의 아래 빈 칸 안에 있다.예 를 들 어 4 는 3 의 오른쪽 위 에 채 워 야 하 는데 3 의 오른쪽 위 에 숫자 1 이 존재 하면 4 는 3 아래 의 빈 칸 에 채 워 야 한다.
다음은 프로그램 코드 입 니 다.

#define N 19
　　int main()
　　{int a[N][N] = {0}, i, j, k, n;
　　　　　　　　　　 /*          0，        */
　　 scanf("%d",&n);          //      （  ）
　　 i = 0;                     //1      0
　　 j = n/2;                  //  1      
　　 a[i][j] = 1;               // 1    
　　 for(k = 2; k <= n*n; k++){ 
　　    if(--i < 0)        //    ，      ，      
　　　　　i += n;    
　　    if(++j == n)      //    ，      ，       
　　　　　j -= n;
　　    if(a[i][j] != 0){          //         
　　      if((i+=2) > n-1)       //   2，      
　　　　　　i -= n;                //           
　　      if((j-=1) < 0)         //   1，      
　　　　　　j += n;                //           
　　    }
　　    a[i][j] = k;              // k  
　　 }
　　 for(i = 0; i < n; i++) {
　　　　for(j = 0; j < n; j++)
　　      printf("%4d", a[i][j]);
　　    printf("
");
　　 }
　　 getch();
　　 return 0;
　　}

게임
   0 ~ 100 사이 의 수 를 무 작위 로 생 성하 여 사용자 가 맞 히 고 5 번 맞 힐 수 있 으 며, 매번 크게 맞 히 거나 작 게 맞 힐 때마다 힌트 를 드 립 니 다.마지막 으로 맞 히 든 틀 리 든 정 답 을 준다.
인 스 턴 스 분석:
난수 생 성 은 실례 11 에 소 개 된 지식 을 이용 할 수 있다.사용자 추측 수 는 최대 5 회 까지 순환 할 수 있 으 며, 한 번 맞 히 면 break.

#include <stdio.h>
　　#include <stdlib.h>
　　#include <time.h>
　　int main()
　　{int n, i, k;
　　 randomize();
　　 n = random(101);
　　 for(i = 1; i <= 5; i++) {
　　　　printf( “
      ，   %d   : ”, 6-i );
　　    scanf(“%d”, &k);
　　    if( k == n )
　　       break;
　　    if(k > n)
　　       printf(“
  ，  !”);
　　    else
　　       printf(“
  ，  !”);
　　 }
　　 if(i <= 5)       // break   
　　   printf(“
   ，   !      %d
”, n);
　　 else              //      
　　   printf(“
  ，   !       %d
”, n);
　　 getch();
　　 return 0;
　　}

2 차원 배열 의 정렬 출력
   10 명의 학생 이 있 고 모든 학생 들 이 세 과목 을 시험 합 니 다. 수학, 영어, 컴퓨터, 키 보드 는 학 번 과 성적 (학 번 과 점 수 는 모두 정수) 을 입력 하고 총 점 의 높 고 낮 음 에 따라 순 서 를 매 겨 출력 합 니 다.
인 스 턴 스 분석:
이 문 제 는 입력, 정렬, 출력 을 완성 해 야 합 니 다.학생 마다 5 가지 데이터 가 있 기 때문에 학 번, 3 개의 성적, 총 점, 10 명의 데 이 터 를 저장 하려 면 2 차원 배열 이 필요 합 니 다.
　　int  a[11][5];    //제 0 행 방치
디자인 아이디어:
배열 의 0 열 은 학 번 을 저장 하고 1 ~ 3 열 은 단 과 를 저장 하 며 4 열 은 총 점 을 저장한다.
모든 데 이 터 는 키보드 에서 입력 하고 순환 으로 이 루어 지 며 순환 하 는 동시에 모든 사람의 총 점 을 계산한다.
정렬 은 선택 법 으로 1 차원 배열 과 달리 이 정렬 은 데 이 터 를 교환 해 야 한다 면 총 점 만 교환 하 는 것 이 아니 라 두 줄 의 데 이 터 를 교환 합 니 다.
다음은 프로그램 코드 입 니 다.

# define NUMBER  10
　　int main()
　　{
　　 int a[NUMBER+1][5], i, j, k, t, n;
　　 for(i = 1; i <= NUMBER; i++){
　　    printf( "     %d      : ", i );
　　    scanf("%d,%d,%d,%d",&a[i][0],&a[i][1],
　　　　　　　　　　　　　　　　&a[i][2],&a[i][3]);
　　    a[i][4] = a[i][1] + a[i][2] + a[i][3];
　　 }
　　 for(i = 1; i < NUMBER; i++) {   //     
　　　　k = i;
　　   for(j = i+1; j <= NUMBER; j++)
　　     if(a[j][4] > a[k][4])
　　　　　　k = j;
　　   for(n = 0; n <= 4; n++){   //     5   
　　     t = a[i][n];
　　　　　a[i][n] = a[k][n];
　　　　　a[k][n] = t;
　　　　}
　　 }
　　 printf("                      
");
　　 for(i = 1; i <= NUMBER; i++)
　　   for(j = 0; j <= 5; j++){
　　     if(j != 5)
　　　　　　　printf(" %3d  ", a[i][j] );
　　     else
　　　　　　　printf(" %3d  
", i );      //    
　　   }
　　 getch();
　　 return 0;
　　}

위 폐 를 찾다
   80 개의 동전 중 하 나 는 가짜 화폐 로 가짜 화폐 가 진짜 화폐 보다 약간 가 볍 습 니 다. 천평 으로 4 번 달 아서 위 폐 를 찾 아 보 세 요.
알림:
천평 양쪽 에 동전 을 넣 을 수 있다.
인 스 턴 스 분석:
천평 으로 4 번 을 달 아 위 폐 를 찾 으 려 면 이렇게 말 해 야 한다.
(1) 동전 을 세 조로 나 누 어 27, 27, 26. 앞의 두 조 의 동전 을 천평 양쪽 에 나 누 어 재 면 위 폐 가 한 조 에 있 는 지 확인 할 수 있 고 위 폐 범 위 는 27 (26) 개의 동전 으로 축소 할 수 있다.
(2) 위 폐 소재 조 를 3 조 9, 9, 9 (또는 9, 9, 8) 로 나 누고 앞의 두 조 를 천평 에 올 려 양 을 재 면 위 폐 가 어느 조 에 있 는 지, 위 폐 범 위 를 9 (8) 개의 동전 으로 축소 할 수 있다.
(3) 3, 3, 3 (또는 3, 3, 2) 을 계속 나 누 면 위 폐 는 3 (2) 개 중 에 있 는 지 확인 할 수 있다.
(4) 1, 1, 1 (또는 1, 1, 0) 을 계속 나 누 면 위 폐 를 찾 을 수 있다.
위 에서 묘사 한 것 은 천평 으로 위 폐 를 찾 는 방법 이지 만 컴퓨터 는 천평 이 아니다. 컴퓨터 프로 그래 밍 으로 이 문 제 를 풀 려 면 프로그램 으로 천평 의 양 을 측정 하 는 과정 을 모 의 해 야 하기 때문에 먼저 수학 모형 을 만들어 야 한다.
천평 은 무 게 를 달 지만 사실은 양쪽 동전 의 총 중량 이 같 는 지 비교 하 는 것 이다.총 무 게 를 계산 할 수 있 도록 우 리 는 하나의 배열 을 정의 하고 모든 요소 가 하나의 동전 의 무 게 를 저장 하 며 진짜 화폐의 무 게 를 1 로 하고 위조지폐 의 무 게 를 0 (진짜 화폐 보다 가 벼 우 면 된다) 으로 한 다음 에 위의 방법 에 따라 4 번 나 누 어 4 번 을 잰다.매번 말 이 끝 날 때마다 k 로 위 폐 가 있 는 그룹 에서 첫 번 째 동전 의 번 호 를 기록 하여 다음 에 그룹 을 나 누 어 k 부터 시작 하도록 한다.
다음은 프로그램 코드 입 니 다.

#include "time.h"
　　#include "stdlib.h"
　　int main()
　　{int i, j, k, m, s1, s2, c[81];
　　 for(i = 1; i <= 80; i++) //         1，    
　　    c[i] = 1;
　　 randomize();
　　 c[random(80)+1] = 0;     //        
　　 k = 1;                        //                
　　 m = 27;                         //    ，  27   
　　 for(i = 1; i <= 4; i++){     //  4 ，     4 
　　    s1 = s2 = 0;                //        ，     
　　    for(j = k; j < m+k; j++){  //            
      s1 += c[j];
      s2 += c[j+m];
    }
　　    if(s1 > s2)            //    2 
　　　　　k += m;
　　    if(s1 == s2)           //    3 
　　　　　 k += 2*m;
　　    m /= 3;                 //    ，      m/3   
　　 }
　　 printf("      ：%d
", k);
　　 getch();
　　 return 0;
　　}

계산 매트릭스 상승
프로그램 컴 퓨 팅 매트릭스 곱 하기: A3×4×B4×2= C3×2
인 스 턴 스 분석:
모든 행렬 은 하나의 배열 로 표시 할 수 있 습 니 다. 배열 c 의 모든 항목 은 누적 결과 이기 때문에 c 배열 의 데 이 터 는 먼저 모두 0 으로 초기 화 해 야 합 니 다.
c 배열 의 한 c [i] [j] 의 값 은 a 의 i 줄 과 b 의 j 열 을 곱 해서 얻 을 수 있 습 니 다.즉: c [i] [j] = a [i] [0] * b [0] [j] + a [1] * b [1] [j] + a [2] * b [2] [j] + a [i] [3] * b [3] [j], 이 식 의 계산 은 순환 으로 이 루어 질 수 있다.

for(k =0; k<=3; k++) 
　　  c[i][j] += a[i][k] * b[k][j];　　

위 에 서 는 배열 c 중의 하 나 를 구 할 뿐 순환 을 이용 하여 모든 데 이 터 를 구 할 수 있 습 니 다.
프로그램 코드:

#define M 3
　　#define K 4
　　#define N 2
　　int main()
　　{int a[M][K] = {3,9,12,10,1,8,6,7,5,4,2,11};
　　　int b[K][N] = {5,8,2,1,7,3,6,4}, c[M][N] = {0};
　　 int i, j, k;
　　 clrscr();
　　　for(i = 0; i < M; i++){
　　   for(j = 0; j < N; j++){
　　     for(k = 0; k < K; k++)
　　       c[i][j] += a[i][k] * b[k][j];
　　     printf(“%5d”, c[i][j]);
　　   }
　　   printf(“
”);
　　 }
　　 getch();
　　 return 0;
　　}

정렬 된 배열 에 데 이 터 를 삽입 합 니 다.
배열 에는 작은 것 부터 큰 것 까지 10 개의 정수 가 저장 되 어 있 으 며, 키 보드 는 하나의 정 수 를 입력 하여 배열 에 삽입 하 였 으 며, 삽 입 된 데 이 터 는 순서대로 배열 되 어 있다.
인 스 턴 스 분석:
해법 1:
정렬 된 데이터 에 데이터 x 를 삽입 하려 면 먼저 x 가 배열 의 어디 에 삽입 해 야 하 는 지 확인 한 다음 에 삽입 해 야 합 니 다.
x 가 어디 에 삽입 되 어야 하 는 지 확인 하려 면 x 를 배열 의 모든 요소 와 순서대로 비교 해 야 합 니 다. 만약 에 x 가 특정한 요소 보다 작 으 면 이 요소 의 위 치 는 x 가 삽입 해 야 할 위치 입 니 다.이 과정 은 아래 코드 로 이 루어 질 수 있다.

for(i = 0; i <= 9; i++)
　　   if(x < a[i])
　　     break;　　

순환 이 끝 난 후에 i 의 값 은 x 삽입 후의 번호 입 니 다. 즉, a [i] 는 x 를 저장 해 야 합 니 다.
그러나 이 때 는 x 를 a [i] 에 저장 할 수 없습니다. 이렇게 하면 a [i] 의 원래 값 을 덮어 씁 니 다.정확 한 방법 은 먼저 a [i] 를 뒤로 옮 긴 다음 에 x 에 저장 하 는 것 이다.그러나 a [i] 를 a [i + 1] 로 옮 기 면 a [i + 1] 을 덮어 쓰 면 어떻게 해결 합 니까?
배열 의 마지막 데이터 부터 뒤로 이동 할 수 있 습 니 다. 즉, 마지막 데 이 터 를 뒤로 이동 한 다음 에 마지막 두 번 째 데 이 터 를 뒤로 이동 할 수 있 습 니 다.
다음 코드 로 구현 가능:

k = i;      // k   i  ，        i     
　　for(i = 9; i >= k; i--)
　　　a[i+1] = a[i];
　　      ，    x   a[k] ：
　　a[k] = x;
　　          ：
　　#include <stdio.h>
　　int main()
　　{int a[11] = {-2,0,3,8,11,15,17,20,24,32};
　　　int x, i, k;
　　 scanf(“%d”, &x);
　　　for(i = 0; i <= 9; i++)
　　　   if(x < a[i])
　　　      break;
　　　k = i;      
　　　for(i = 9; i >= k; i--)  /*  k            */
　　　　a[i+1] = a[i];
　　　a[k] = x;           // x  
　　　for(i = 0; i <= 10; i++)
　　　   printf(“%5d”, a[i]);
　　　getch();
　　　return 0;
　　}

해법 2:
배열 의 요 소 를 마지막 부터 x 와 순서대로 비교 하고 배열 요소 가 x 보다 크 면 x 보다 크 지 않 은 요소 나 모든 요 소 를 비교 할 때 까지 뒤로 이동 합 니 다.

for(i = 9; i >= 0 && a[i] > x; i--)
　　   a[i + 1] = a[i];　　

순환 이 끝 날 때 두 가지 상황 이 존재 합 니 다.
(1) 하나의 요 소 를 만 나 a [i] 가 x 보다 크 지 않 게 한다. 이때 x 는 a [i + 1] 에 삽입 해 야 한다.
(2) 모든 요 소 를 비교 하여 x < 0 순환 을 종료 하고 x 는 a [0], 즉 a [i + 1] 에 삽입 해 야 한다.
두 가지 상황 모두 a [i + 1] = x 를 사용 할 수 있다.삽입 을 완료 합 니 다.
해법 2 의 주요 코드 는:

for(i = 9; i >= 0 && a[i] > x; i--)
　　   a[i+1] = a[i];
　　　a[i+1] = x;