Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 확장된 미디 정리(Extended Midy's Theorem)

미디 정리(Midy's Theorem)는 순환소수의 흥미로운 성질을 설명하는 수학 정리입니다. 분수 n/p(n은 임의의 정수, p는 소수)의 소수 전개가 짝수 자릿수의 순환 마디를 가질 때, 순환 마디를 두 부분으로 나누어 더하면 999…9처럼 9로만 이루어진 수가 된다는 내용입니다.

확장된 미디 정리(Extended Midy's Theorem)는 이 정리를 일반화한 형태입니다. 순환 마디를 m자리씩 여러 조각으로 나눈 뒤 각 조각의 값을 모두 더하면, 그 합은 반드시 10m − 1의 배수가 됩니다.

예를 들어 1/17 = 0.0588235294117647…(순환 마디 16자리)인 경우, 순환 마디를 4자리씩 나누면 0588 + 2352 + 9411 + 7647 = 19998 = 2 × 9999가 되어 확장된 미디 정리가 성립함을 확인할 수 있습니다.

알고리즘 동작 방식

구현은 크게 두 단계로 이루어집니다.

1단계 – 순환 소수 찾기(findDecimalValue): 분자와 분모를 받아 나머지 기반의 장제법(long division)을 시뮬레이션합니다. 해시 맵(unordered_map)을 사용해 이미 등장한 나머지를 추적하여 순환 주기를 감지하고, 순환 마디에 해당하는 문자열을 반환합니다. 순환 소수가 없다면 "-1"을 반환합니다.

2단계 – 정리 검증(ExtendedMidysAlgo): 먼저 isPrime 함수로 분모가 소수인지 확인합니다. 소수가 아니거나 순환 마디의 길이가 홀수이거나 m으로 나누어떨어지지 않으면 정리를 적용할 수 없습니다. 조건을 만족하면 순환 마디를 m자리씩 잘라 각 부분의 합을 구한 뒤, 그 합이 10m − 1로 나누어떨어지는지 검사합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

// 분수의 순환 소수 부분을 계산하는 함수
string findDecimalValue(int num, int den) {
    string res;
    unordered_map<int, int> mp;
    int rem = num % den;

    while ((rem != 0) && (mp.find(rem) == mp.end())) {
        mp[rem] = res.length();
        rem = rem * 10;
        int part = rem / den;
        res += to_string(part);
        rem = rem % den;
    }
    return (rem == 0) ? "-1" : res.substr(mp[rem]);
}

// 소수 판별 함수
bool isPrime(int n) {
    for (int i = 2; i <= n / 2; i++)
        if (n % i == 0)
            return false;
    return true;
}

// 확장된 미디 정리 검증 함수
void ExtendedMidysAlgo(string str, int n, int m) {
    if (!isPrime(n)) {
        cout << "분모가 소수가 아니므로 확장된 미디 정리를 적용할 수 없습니다.";
        return;
    }

    int l = str.length();
    if (l % 2 == 0 && l % m == 0) {
        int part[m] = { 0 }, sum = 0, res = 0;
        // 순환 마디를 m자리씩 나누어 저장
        for (int i = 0; i < l; i++) {
            int var = i / m;
            part[var] = part[var] * 10 + (str[i] - '0');
        }
        // 각 조각 출력 및 합 계산
        for (int i = 0; i < m; i++) {
            sum = sum + part[i];
            cout << part[i] << " ";
        }
        cout << endl;
        res = pow(10, m) - 1;
        if (sum % res == 0)
            cout << "확장된 미디 정리가 성립합니다!";
        else
            cout << "확장된 미디 정리가 성립하지 않습니다!";
    }
    else if (l % 2 != 0) {
        cout << "순환 마디의 길이가 홀수이므로 확장된 미디 정리를 적용할 수 없습니다.";
    }
    else if (l % m != 0) {
        cout << "순환 마디를 m자리씩 나눌 수 없습니다.";
    }
}

// 드라이버 코드
int main()
{
    int numr = 1, denr = 17, m = 4;
    string res = findDecimalValue(numr, denr);
    if (res == "-1")
        cout << "이 분수는 순환 소수를 갖지 않습니다.";
    else {
        cout << "순환 소수 = " << res << endl;
        ExtendedMidysAlgo(res, denr, m);
    }
    return 0;
}

실행 결과

순환 소수 = 0588235294117647
588 2352 9411 7647
확장된 미디 정리가 성립합니다!

결과 해석

분수 1/17의 순환 마디는 16자리인 '0588235294117647'입니다. 이를 4자리씩 나눈 588, 2352, 9411, 7647의 합은 19998이며, 이는 104 − 1 = 9999의 배수(2 × 9999)입니다. 따라서 확장된 미디 정리가 성립함을 확인할 수 있습니다.

이 알고리즘은 시간 복잡도 측면에서 순환 마디 길이 L에 대해 O(L)로 매우 효율적이며, 순환소수의 수학적 성질을 프로그래밍으로 검증하는 좋은 예제가 됩니다.