C_C++/기초_알고리즘_문제

(C언어) 개미 수열 look and say sequence

고니자니 2022. 11. 24. 18:38
반응형

#개미수열 #look and say sequence

 

1 11 12 1121 122111 112213 ...

 

 

개미 수열

읽고 말하는 대로 다음 항을 도출하는 수열이다. 보통은 초항이 1이지만, 다른 수를 초항으로 설정하기도 한다. 보고 말하기 수열이라고도 하며, 프랑스의 유명 소설가 베르나르 베르베르의 소설 <개미>에 등장한다고 하여 개미 수열이라고도 한다. 이 수열은 일상적 언어를 사용한 구술적인 방식으로 정의되기에, 엄밀한 수학적 표현으로 정의되는 여타 수열과 달리 일반항이나 점화식이 아직까지 알려지지 않았다.

콘웨이의 생명 게임으로 유명한 존 호튼 콘웨이가 만들었다.

 

 

개미수열은

[1행] 1입니다.

[2행] 11 -- 이전 항에서 1이 1개 연속이라는 의미입니다.

[3행] 12 -- 이전 항이 1이 2개 연속되었다는 의미입니다.

[4행] 1121 -- 이전 항이 1이 1개, 2가 1개 연속되었다는 의미입니다.

[5행] 122111 -- 이전 항이 1이 2개, 2가 1개, 1이 1개 연속되었다는 의미입니다.

 1
 1 1
 1 2
 1 1 2 1
 1 2 2 1 1 1
 1 1 2 2 1 3
 1 2 2 2 1 1 3 1
 1 1 2 3 1 2 3 1 1 1
 1 2 2 1 3 1 1 1 2 1 3 1 1 3
 1 1 2 2 1 1 3 1 1 3 2 1 1 1 3 1 1 2 3 1

 

 

#include<stdio.h>
#define N   10   // 라인수

int main() {
    int a[100] = { 0, };
    int b[100] = { 0, };
    int n, count, i, j;
    a[0] = 1;      // 맨 처음 값


    printf("%2d\n", a[0]);

    for (int x = 1; x < N; x += 1) {
        i = 0;
        j = 0;
        count = 1;

        while (a[i] != 0) {
            if (a[i + 1] == a[i]) {
                count++;
            }
            else {
                b[j] = a[i];
                printf("%2d", b[j]);
                j++;

                b[j] = count;
                printf("%2d", b[j]);
                j++;
                count = 1;
            }
            i += 1;
        }

        for (i = 1; i < 100; i++) {
            a[i] = b[i];
            b[i] = 0;
        }

        printf("\n");
    }

    return 0;
}

 

 

반응형