[C로 쓴 자료구조론] 1장 연습문제-5번(비둘기집) 풀이

 

 

 

 

 

 

 

문제

---

5. 비둘기 집 원칙(pigeon hole principle)이란 함수가 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 a!=b이고 f(a)=f(b)인 2개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력 값이 상이하면서 함수 값이 같은 a, b를 찾는 C프로그램을 작성하여라.

---

 

 

확통시간에 어디선가 본것같은 이 느낌.... 

x와 y를 정해놓고 그걸 찾는 알고리즘을 짜면 되겠죠

 

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX 30 // 배열의 최대 크기 
#define FUN(x) (x*x - 100*x + 8) // 임의의 함수 정의

int find(int result, int n);
 
int output[MAX] = { 0 }; // 각 변수의 함수결과값 저장
int inputs[MAX] = { 0 }; // 함수에서 계산된 변수 저장
 
void main()
{
  int i, equal; // equal: 같은 함수값이 있는지 확인하는 변수
  int num, count = 0; // num: random으로 생성하는 입력값, count: 단순 카운팅 변수
  int val, result; // val: 같은 함수값을 갖는 이전 입력값
 
  srand((unsigned)time(NULL));
  while (count < MAX)
  {
    equal = 0;
    num = (int)((double)rand() / RAND_MAX * 100); // 0~99 난수 생성
 
    // 이미 사용된 입력값인지 확인한다. 우리는 같은 출력값을 가지는 다른 입력 둘을 찾고 있다.
    for (i = 0; i < count; i++)
      if (inputs[i] == num) // 기존의 입력값 배열에 내가 입력하려는 값이 있는지 확인한다.
      {
        equal = 1;
        break;
      }
    if (equal) // 같은 값이 있다면 while문의 처음으로
      continue;
 
    result = FUN(num); // 함수에 num을 대입한 결과값 저장
 
    // n개보다 작은 결과값, 즉 같은 결과값이 있다면 value를 리턴하고
    // 없다면 -1 리턴
    if ((val = find(result, count)) == -1) { // val에는 -1 또는 values[i] 값이 담긴다. (이전 입력값)
      output[count] = result; // 결과값을 배열에 저장
      inputs[count++] = num; // 변수를 배열에 저장
    }
    else {
      printf("a = %d, b = %d\n", val, num); // val: 같은 함수값을 갖는 이전 입력값, num: 현재 입력값
      break;
    }
  }
}
 
int find(int result, int n)
{
  int i;
  for (i = 0; i < n; i++)
    if (result == output[i])
      return inputs[i]; // 그 값을 찾은 경우 전의 입력값을 리턴한다.
  return -1; // 찾는 값이 없을 경우
}