숫자 순환 알고리즘

숫자 순환 알고리즘

 

숫자 순환 알고리즘은 주어진 숫자 N 제곱수 P가 주어질 경우

 

각 숫자 N의 자릿수에 P제곱을 하고 더한 값이 각 원소가 됩니다.

 

무슨 말이냐면

 

숫자 57 제곱수 2가 주어지면

 

5^2+7^2=74가 됩니다. 74는 7^2+4^2=65가 됩니다. 이렇게 57, 74, 65, ...원소를 꾸려나갑니다.

 

이런식으로 하다보면 순환이 된다는 것을 발견합니다.

 

이 알고리즘은 비순환 부분의 개수를 찾는 것으로 순환 되는 지점 이전 원소들의 개수를 구하면 됩니다.

 

우선 입력을

<input.txt>

2          (Case Number)

57 2       (N P)

638 2      (N P)

 

이렇게 받는다고 칩시다.

 

입력 형태는

첫 행은 케이스 수

두 행부터 N과 P 입니다.

조건=>  숫자 N 제곱수 P 케이스 수 T

 

 

 

 

입력받은 숫자 값 만큼 곱셈을 반복하여 숫자를 계속 생성해야합니다.

 

그러기 위해서는 우선 제곱수(P) 만큼 for문을 돌려야겠죠?

 

digit은 자릿수로 칩시다. 예를 들어 15라눈 숫자를 10으로 나눈 몫은 십의 자리 수, 나머지는 일의 자리 수 입니다.

 

if(powerNumber>2){

for(i=2; i<=powerNumber; i++)

{

digit *= digit;

}

}

 

즉 digit이 5이고 제곱수 2이면 5를 2번 곱해야하므로 5 *= 5 입니다.

 

여러분들은 배열에서 검사하여 어떤 값과 같으면 끝내는 프로그램들을 많이 짰을 겁니다.

 

예를 들어

for(i=0; i<10; i++)

{

if(A == arry[i])

break;

}

 

이러한 코드는 시간이 굉장히 오래걸리며 최악의 경우 10번까지 검사를 하게되겠죠 ...

 

이를 방지하기 위해 예전에 포스팅 한 계수정렬 기억하실지 모르겠지만 계수정렬에서는 해당 배열의 값을 인덱스로 사용하는

 

원리를 이용했습니다.

 

즉 1부터 10000까지 숫자 중에 해당 숫자가 몇번 카운트 되는지 하기 위해서 counter라는 배열 인덱스에 arry[]배열 값을 넣

 

어서 counter[1]은 1이 나온 횟수로 구했었죠.

 

이 원리가 중요합니다.

 

즉

for(i=0; i<10000; i++){

counter[arry[i]]++;

}

 

이렇게 되면 counter[57]은 57이 몇번 나왔는지 알 수 있겠죠

 

이 코드를 이용해서 배열의 인덱스로 사용하게 되면

 

한번에 검색이 가능합니다.

 

마지막으로 반복되는 숫자가 나타날 때 까지 몇 개의 숫자가 있는지 구해야합니다.

 

즉 연산으로 구한 숫자가 초기 메모장에서 받아온 숫자와 같으면 반복되는 것이므로

 

반복 된다 싶으면 for문을 빠져나오면 됩니다.

 

for(i=0; i<Solution; i++){
    if(initNumber==calculatedNumber[i])

break;

}

 

전체 코드를 봅시다.

#include <stdio.h>



#define MAX_SIZE 10000

 

int calculatedNumber[MAX_SIZE]; // 연산으로 구한 숫자

int foundFlag[MAX_SIZE]; // 발견 했는지 확인용 플래그

 

int main(void)
{
 int tc, testCases, index, initNumber, powerNumber, Solution, tempNumber;
 int i;
 FILE *fp = NULL;

 freopen_s(&fp, "input.txt", "r", stdin);
 setvbuf(stdout, NULL, _IOFBF, 1024);
 scanf_s("%d", &testCases); //테스트 케이스 수 얻어오기

 for (tc = 0; tc < testCases; tc++)
 {
  Solution = 0;

  //초기 값 연산 값을 메모장으로부터 입력받음.
  scanf_s("%d %d", &initNumber, &powerNumber);

  calculatedNumber[Solution++] = initNumber;

  while (1)
  {
   tempNumber = 0;

   while (initNumber)
   {
    int digit = (initNumber % 10); //일의자리숫자
    initNumber = (initNumber / 10); //십의 자리숫자

    //주어진 powerNubmer 값만큼 곱함

    if (powerNumber >= 2)
    {
     for (i = 2; i <= powerNumber; i++)

      digit *= digit;

    }
    tempNumber += digit;
    printf("digit : %d, tempNumber : %d\n", digit, tempNumber);
   }

 

   initNumber = tempNumber;

   if (foundFlag[initNumber] == 1)
    break;


   foundFlag[initNumber] = 1;
   printf("foundFlag initNumber: %d\n", initNumber);
   calculatedNumber[Solution++] = initNumber;

   printf("calcuatedNumber[%d] : %d, initNumber: %d\n", Solution, calculatedNumber[Solution], initNumber);
  }
   for (i = 0; i < Solution; i++)
   {
    if (initNumber == calculatedNumber[i])
     break;
   }

   printf("%d\n", i);
   for (i; i < Solution; i++)

    foundFlag[calculatedNumber[i]] = 0;
  
 }
 
 return 0;
}