[알고리즘문제] 숫자 대응

이번에도 알고리즘 프로그래밍 문제입니다.

한 번 풀어보아용~

문제!!

N이 n이하인 양의 정수 집합 {1, 2, 3, ․․․, n}을 나타낸다고 하자. 우리는 다음 조건을 만족하는 일대일 대응 함수 F: N → N을 구하고자 한다.

조건: 각각의 i에 대해서 i+F(i) = 2k를 만족하는 정수 k, k≥1가 존재한다, 1≤F(i)≤n.

즉, N에 속한 모든 i에 대해 i와 그에 대응하는 함수값 F(i)를 더한 값이 2의 거듭제곱(power)인 형태의 값이 되어야 함을 말한다. 예를 들어 n=5인 경우에 위의 조건을 만족하는 일대일 대응 함수가 다음과 같이 존재한다.

위의 예에서 1+1 = 21, 2+2 = 22, 3+5 = 23, 4+4 = 23, 5+3 = 23이므로 이러한 대응이 위의 조건을 만족함을 알 수 있다.

n이 주어졌을 때, 위의 조건을 만족하는 일대일 대응 함수를 출력하는 프로그램을 작성하시오.

답(이 아닐수도..ㅎㅎㅎ)

- 소스 코드 -

#include <stdio.h>

#include <conio.h>

#define USABLE 0 // 사용가능한공간

#define UNUSABLE 1 // 사용된공간

int data[1001] = {0, }; // n인자까지의배열만을사용. 일대일대응을체크하기위해, 집합내에같은숫자가두개중복되는것을방지하기위해사용

int result[1001] = {0, }; // 결과값을저장하는배열

int n; // 입력받은값

void Calculate();

void InputFile();

void OutputFile();

void main()

{

        InputFile(); // 파일로부터데이터얻기

        Calculate(); // 결과값구하기

        OutputFile(); // 파일에결과쓰기

        getch();

}

void Calculate()

{

        int i, j, square = 2; // i,j : for문을위한임시변수, square : 기준이되는2의제곱수

        while(1) // 최대9번이상반복되지않음1000이하의2의제곱수중가장큰수는2^9이므로

        {

               if(square <= n) square *= 2; // 입력받은n값보다크면서가장가까운2의제곱수구하기

               else break; // 루프빠져나가기

        }

        for(i = n; i >= 1; i--) // 계산은큰수부터작은수로거꾸로구해나간다.

        {

               if(i < (square / 2)) square /= 2; // i가현재설정된2의제곱수보다작은값이라면square에현재설정된2의제곱수보다한단계낮은2의제곱수저장

               if(data[i] != USABLE) continue; // 이미사용된숫자라면

               for(j = 1; j <= n; j++) // i와함께2의제곱수에맞추기위한j를찾아낸다.

               {

                       if(data[j] != USABLE) continue; // 이미사용된숫자라면

                       if((i + j) == square) // i와j의합을통해적절한2의제곱수가되었다면

                       {

                              data[i] = data[j] = UNUSABLE; // 사용된숫자이므로다시사용하지못하도록1로체크

                              result[i] = j, result[j] = i; // 결과배열에각각의적절한결과값저장

                       }

               }

        }

        printf("작업이완료되었습니다.\n");

}

void InputFile() // 파일로부터입력받기

{

        FILE *fp; // 파일포인터개체

        fp = fopen("Input.txt", "r"); // 파일열기

        fscanf(fp, "%d", &n); // n 값을입력받는다.

        fclose(fp); // 파일닫기

}

void OutputFile()

{

        FILE *fp; // 파일포인터개체

        fp = fopen("Output.txt", "w"); // Output.txt 파일을쓰기형식으로열기

        fprintf(fp, "%d\n", n); // 초기입력값출력

        for(int x = 1; x <= n; x++) // 결과출력

               fprintf(fp, "%d\n", result[x]);

        fclose(fp); // 파일닫기

}

테스트 (샘플)

* n 으로 8이 입력된 경우 – 결과 : 8 7 6 5 4 3 2 1 8

n = 8;

square = 16 (n 보다 크면서 가장 근접한 2의 제곱수를 얻어냄)

i ) 첫번째 외부 루프 실행 i = 8

 j = 1 (X), j = 2 (X) … j = 8 (O, 8 + 8 = 16(2^4), 즉 square값과 동일)

data[8] = data[8] = UNUSABLE, result[8] = result[8] = 8

ii) 두번째 외부 루프 실행 i = 7

i 가 8(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 8

j = 1 (O, 7 + 1 = 8(2^3), 즉 square값과 동일)

data[7] = data[1] = UNUSABLE, result[7] = 1, result[1] = 7

iii) 세번째 외부 루프 실행 i = 6

j = 1(X, 1은 UNUSABLE상태), j = 2(O, 6 + 2 = 8(2^3), 즉 square값과 동일)

data[6] = data[2] = UNUSABLE, result[6] = 2, result[2] = 6

iv) 네번째 외부 루프 실행 i = 5

j = 1(X, UNUSABLE), j = 2(X, UNUSABLE), j = 3(O, 5 + 3 = 8(2^3), 즉 square값과 동일)

data[5] = data[3] = UNUSABLE, result[5] = 3, result[3] = 5

v) 다섯번째 외부 루프 실행 i = 4

j = 1, j = 2, j = 3(모두X, 이미 UNUSABLE), j = 4(O, 4 + 4 = 8(2^3), 즉 square값과 동일)

data[4] = data[4] = UNUSABLE, result[4] = result[4] = 4

vi) 여섯번째 외부 루프 실행 i = 3

i 가 4(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 4

이미 i = 3은 네번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.

vii) 일곱번째 외부 루프 실행 i = 2

이미 i = 2는 세번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.

viii) 여덟번째 외부 루프 실행 i = 1

i 가 2(square/2) 보다 작은 값을 가지므로 square = square / 2 로 변경, square = 2

이미 i = 1은 두번째 루프를 돌 때 적절한 값을 얻었으므로 건너 뜀.

결과 값 (result배열 값 ) 출력 : 8 7 6 5 4 3 2 1 8

소스 코드 및 실행 파일 받기

mapping.zip