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

게임
n. 아이 가 한 바퀴 를 돌 고 1 부터 숫자 를 알 리 고 k 에 도착 한 사람 은 물 러 나 고 나머지 는 다시 1 번 숫자 에서 물 러 나 거나 k 에 게 물 러 날 때 까지 m 명의 아이 만 남 았 습 니 다. 마지막 에 남 은 사람 은 어떤 사람 이 냐 고 물 었 습 니 다.
인 스 턴 스 분석:
이 문 제 는 여기 서 배열 의 구 해 를 통 해 링크 로 구 해 내 는 방법 으로 제1 7 장 알고리즘 과 데이터 구조 인 스 턴 스 에 넣 을 것 이다.
디자인 사고: 배열 요소 로 아 이 를 모 의 한다.하나의 배열 을 정의 합 니 다. 모든 요 소 는 하나의 수 치 를 아이의 번호 로 저장 한 다음 에 첫 번 째 요소 부터 번 호 를 알 리 고 k 에 신고 한 사람 은 번 호 를 0 으로 표시 합 니 다.번호 가 0 인 사람 은 번호 가 0 인 사람 은 더 이상 번호 에 참가 하지 않 는 다.배열 의 모든 요소 가 숫자 를 알 린 후에 다시 배열 의 머리 부터 숫자 를 알 리 고 반복 해서 동그라미 에 m 명의 아이 만 남 을 때 까지 합 니 다.

#define N 100
　　int main()
　　{int a[N], n, m, k;
　　　int i, count, j;
　　 scanf(“%d%d%d”, &n, &k, &m);
　　 for(i = 1; i <= n; i++)
　　   a[i] = i;
　　 j = n;                         //j：       
　　 count = 0;                    //      ，        1
　　 i = 1;                        //    1              
　　 while(j > m){
　　   if(a[i] != 0){             //        
　　     count++;                  //    
　　     if(count == k){          //   k
　　       a[i] = 0;               //    
　　　　　　count = 0;              //  ，     1    
　　       j--;                     //     1
　　     }  
　　   }
　　　 i++;                         //         
　　   if(i > n)                   //       
　　     i = 1;                    //       
　　 }
　　 for(i = 1; i <= n; i++)
　　　　if(a[i] != 0)
　　　　  printf(“%4d”, a[i]);
　　 getch();
　　 return 0;
　　}

클 록 프로그램
시간, 분, 초, 그리고 지난 오 후 를 포함 하여 시스템 시간 을 표시 하 는 프로그램 을 만 듭 니 다.
인 스 턴 스 분석:
이 인 스 턴 스 는 시스템 시간 과 관련 된 함수 가 필요 합 니 다.프로그래머 의 편 의 를 위해 Turbo C 는 dos. h 에서 두 개의 구조 체 를 정의 하여 시간 과 날짜 처리 에 사용 합 니 다.

struct time{
　　  unsigned char ti_min;    // 
　　  unsigned char ti_hour;   //  
　　　unsigned char ti_hund;   //   
　　　unsigned char ti_sec;    // 
　　};
　　struct date{
　　  int da_year;           // 1900      
　　  char da_day;          //  
　　  char da_mon;         //  
　　};

Turbo C 는 time. h 에서 시간 과 관련 된 함 수 를 제공 합 니 다.
　　（1）char *ctime(const time_t *clock);
역할: clock 이 가리 키 는 시간 을 다음 과 같은 형식의 문자열 로 바 꿉 니 다: Mon Nov 21 11: 31: 54 2009\0。마지막 두 문 자 는 줄 바 꿈 문자 와 빈 문자 입 니 다.
　　（2）char *asctime(const struct tm *t);
역할: t 가 가리 키 는 시간 을 다음 과 같은 형식의 문자열 로 바 꿉 니 다: Mon Nov 21 11: 31: 54 2009\0。
　　（3）double difftime(time_t time2, time_t time1);
역할: 두 시간의 차 이 를 되 돌려 줍 니 다. 단위: 초.
   （4）struct tm *localtime(long *clock);
역할: clock 이 가리 키 는 시간 을 현지 표준 시간 으로 바 꾸 고 tm 구조 지침 으로 되 돌려 줍 니 다.

long time(long *p);

   역할: 1970 년 1 월 1 일 새벽 부터 지금까지 지 나 는 초 수 를 주 고 이 값 을 p 가 가리 키 는 변수 에 기록 합 니 다.

int stime(long *p);

   역할: p 가 가리 키 는 시간 을 컴퓨터 에 기록 합 니 다.
   그리고 dos. h 에서 다음 과 같은 시간 과 관련 된 함 수 를 제공 합 니 다.

void gettime(struct time *timep);

   역할: 컴퓨터 시스템 의 시간 을 timep 가 가리 키 는 구조 체 변수 에 기록 합 니 다.

settime(struct time *timep);

   역할: 시스템 시간 을 timep 가 가리 키 는 시간 으로 설정 합 니 다.
   이 예 는 함수 gettime () 에 만 사 용 됩 니 다.
   프로그램 코드:

#include <dos.h>
#include <conio.h>
int main()
{struct time curtime;
 float cur_hour, cur_min, cur_sec;
 clrscr();
 do{
   printf("The current time is:
");
   gettime(&curtime);            //      
   if(curtime.ti_hour <= 12)
     printf("AM ");
   else{
     printf("PM ");
     curtime.ti_hour -= 12;
   }
   if(curtime.ti_hour < 10)
     printf("0");
   printf("%d:", curtime.ti_hour);
   if(curtime.ti_min < 10)
     printf("0");
   printf("%d:", curtime.ti_min);
   if(curtime.ti_sec < 10)
     printf("0");
   printf("%d", curtime.ti_sec);
   sleep(1);                    //  conio.h   
   clrscr();
 }while(!kbhit());
 return 0;
}

간단 한 계산기 (1)
   프로 그래 밍, 사용자 가 입력 한 네 가지 연산 식 의 값 을 계산 하 는 데 사용 되 며, 덧셈 과 곱셈 만 포함 하고 괄호 는 포함 되 지 않 습 니 다.
인 스 턴 스 분석:
표현 식 에는 가감 승제 가 포함 되 어 있 으 며, 승제 의 우선 순위 가 가감 보다 높다.
우 리 는 키보드 입력 - 3.12 + 2 * 3.5 / 4 + 8 / 2 - 3 * 6 을 예 로 들 어 알고리즘 을 설명 합 니 다.
식 의 2 * 3.5 / 4, 8 / 2 와 3 * 6 을 먼저 계산 해 야 합 니 다. 계산 이 끝 난 후에 전체 표현 식 은 4 개의 데이터 항목 만 있 고 나머지 문 제 는 간단 합 니 다.이 를 위해 우 리 는 전체 표현 식 을 4 부분 (4 조각) 으로 나 눌 수 있 습 니 다. 블록 과 블록 사 이 는 반드시 플러스 마이너스 로 연 결 됩 니 다. 각 조각 중간 에 곱 하기 만 하고 플러스 와 마이너스 가 없습니다.
실제로 각 조각의 값 을 먼저 계산 할 필요 가 없다. 표현 식 을 계산 하 는 과정 에서 한 조각 을 만 날 때마다 이 조각의 결 과 를 먼저 계산 한 다음 에 앞의 계산 결과 와 가감 연산 을 하고 뒤의 블록의 값 은 사용 할 때 계산 할 수 있다.
구체 적 인 계산 방법 은:
프로그램 이 먼저 변수 result 를 정의 하고 0 으로 초기 화 합 니 다.
처음부터 모든 조각 을 처리 합 니 다: 하나의 데 이 터 를 추출 합 니 다. 만약 에 데이터 뒤에 곱 하기 (제외) 가 있 으 면 이 블록 의 계산 이 끝나 지 않 았 음 을 나타 내 고 두 번 째 데 이 터 를 계속 추출 하여 첫 번 째 데이터 와 곱 하기 (제외) 연산 을 한 다음 에 뒤의 연산 자 를 봅 니 다. 만약 에 '*' 또는 '/' 이면 데 이 터 를 계속 추출 하고 계산 합 니 다... 연산 자 '+' 를 만 날 때 까지...'-' 또는 빈 문자 까지.
연산 자 '+', '-' 또는 빈 문 자 를 만나면 이 블록 의 계산 이 끝 났 음 을 나타 내 고 계산 결 과 를 result 에 누적 할 수 있 습 니 다.
표현 식 이 끝 날 때 까지 위의 방법 을 반복 합 니 다.result 가 마지막 결과 다.
프로그램 코드:

#include "stdio.h"
　　#include "stdlib.h"
　　float get_num(char **);             
　　int main()
　　{char a[80];
　　 int sign = 1;      //        ‘+’，sign = 1，  ‘-’，sign = -1
　　 float result = 0;
　　　char *p;            //          
　　 clrscr();
　　 gets(a);
　　 p = a;
　　 if(*p == '-') {     //          ‘-’
　　    sign = -1;        //    
　　    p++;        
　　 }
　　 while(*p != 0) {           //       ，   
　　    float  m;                //m           
　　　　m = sign*get_num(&p);   //get_num     ，p     
　　    while( *p == '*' || *p == '/' ){ //          
　　       if( *p == '*' ) {
         p++;
         m *= get_num(&p);
       }
　　       else {
          int div;
　　　　　　　p++;
          div = get_num(&p);
          if( div == 0 ) {
　　　　　　　　　printf("  ！   0！
");
             exit(1);
          }
          else
             m /= div;
       }
　　    }
　　    if(*p != '+' && *p != '-' && *p != 0){
　　       printf("  ！      ：%c
", *p);
　　       exit(0);
　　    }
　　    result += m;    //               result 
　　    if(*p == '+'){
　　       sign = 1;
　　       p++;
　　    }
　　    else if(*p == '-') {
　　       sign = -1;
　　       p++;
　　    }
　　    else          //     ，    
　　      break;
　　   }
　　 printf("The result is %f
", result);
　　 getch();
　　 return 0;
　　}
　　float get_num(char **pp)    //pp  p
　　{float x = 0, m = 10;
　　 if(**pp != '.' && (**pp <'0' || **pp >'9') ) {
　　    printf("  ！              
");
　　    exit(1);
　　 }
　　 while(**pp >= '0' && **pp <= '9') {
　　　　x = x*10 + **pp - 48;
　　    (*pp)++;
　　 }
　　 if(**pp == '.') {
　　    (*pp)++;
　　    while(**pp >= '0' && **pp <= '9') {
　　       x += (**pp - 48)/m;
　　       (*pp)++;
　　       m *= 10;
　　    }
　　 }
　　 return x;
　　}

간단 한 계산기 (2)
   프로 그래 밍, 사용자 가 입력 한 네 가지 연산 식 의 값 을 계산 하 는 데 사용 되 며, 가감 승제 와 괄호 를 포함 합 니 다.
인 스 턴 스 분석:
이 실례 와 상례 의 차 이 는 표현 식 에 괄호 가 있다 는 것 이다.사실 모든 괄호 의 내용 은 하나의 단독 표현 식 (괄호 가 있 을 수도 있 습 니 다) 으로 볼 수 있 습 니 다. 이 점 을 고려 하여 우 리 는 프로그램 을 재 귀적 호출 방식 으로 쓸 수 있 습 니 다. 괄호 를 만나면 괄호 에 있 는 표현 식 의 값 을 스스로 계산 할 수 있 습 니 다.해당 프로그램 코드 는 다음 과 같 습 니 다.

#include "stdio.h"
　　#include "stdlib.h"
　　float get_num(char **);
　　float calculate(char **);
　　int main()
　　{char a[80];
　　 float result;
　　 char *p;
　　 clrscr();
　　 gets(a);
　　 p = a;
　　 result = calculate(&p);
　　 printf("%f
", result);
　　 getch();
　　 return 0;
　　}
　　float calculate(char **p)
　　{float result = 0;
　　 int sign = 1;
　　 if(**p == '-') {
　　    sign = -1;
　　    (*p)++;
　　 }
　　 while(**p != 0 && **p != ')' ) {
　　   float  m;
　　   if(**p == '(' ) {
　　      (*p)++;
　　      m = sign*calculate(p);  //               
　　   }
　　   else
　　      m = sign*get_num(p);
　　   while(**p == '*' || **p == '/') {
　　     if(**p == '*') {
       (*p)++;
       if(**p == '(') {
          (*p)++;
          m *= calculate(p);  //               
       }
       else
         m *= get_num(p);
     }
　　     else {     
       int div;
       (*p)++;
       if(**p == '(') {
         (*p)++;
         div = calculate(p); //               
       }
       else
         div = get_num(p);
       if(div == 0) {
          printf("diveide by 0!
");
          exit(1);
       }
       else
          m /= div;
     }
　　   }
　　   if(**p != '+' && **p != '-' && **p != 0 && **p != ')'){
　　       printf("illege character: %c
",**p);
　　       exit(0);
　　   }
　　   result += m;
　　   if(**p == '+') {
　　      sign = 1;
　　      (*p)++;
　　   }
　　   else
　　     if(**p == '-' ) {
       sign = -1;
       (*p)++;
     }
　　     else
       if(**p == ')' ) { //     ，           
          (*p)++;
          break;
       }
       else
          break;
　　 }
　　 return result;
　　}
　　float get_num(char **p)
　　{float n = 0, m = 10;
　　 if(**p != '.' && (**p <'0' || **p >'9')) {
　　    printf("get num error!
");
　　    exit(1);
　　 }
　　 while(**p >= '0' && **p <= '9') {
　　    n = n*10 + **p - 48;
　　    (*p)++;
　　 }
　　 if(**p == '.') {
　　    (*p)++;
　　    while(**p >= '0' && **p <= '9') {
　　       n += (**p - 48)/m;
　　       (*p)++;
　　       m *= 10;
　　    }
　　 }
　　 return n;
　　}