7의 배수 판정 프로그램

너무도 무의미한 0과 1을 제외하고, 10이상의 수도 제외하고,

2에서 9까지의 숫자의 배수인지 판정하는 간단한 판정법은 알려져 있지만,

특이하게 7의 배수는 판정법이 별로 알려진 것이 없다.

2와 5, 10의 배수는 끝자리만 확인하면 되고,

3의 배수는 각 자리를 다 더해서 3의 배수인지 확인, 6과 9는 3의 바리에이션이므로 생략,

4와 8의 배수는 각각 끝에서 두자리, 세자리가 4와 8의 배수인지 확인하면 된다.

7의 경우는 딱히 알려진 방법이 없는데, 네이버캐스트에서 이를 자세히 소개하고 있다.

네이버캐스트 :: 7의 배수 판정법

여기에서는 위의 링크에 나온 내용을 C++를 사용하여 프로그램으로 만들어 보았다.

네이버야, 네이버야, 소스를 좀 쉽게 올릴수 있게 해주지 않으련? ~_~

1 /*   2  * main.cc   3  *   4  *  Created on: 2011. 4. 4.   5  *      Author: strawberryit   6  *   7  *      7의 배수 판정법   8  *      자세한 설명은 네이버캐스트  '7의 배수 판정법' 참고   9  *      http://navercast.naver.com/contents.nhn?contents_id=1541  10  *  11  *        스택, 큐 구현하기 귀찮아서 CPP로 작성  12  *        직접 구현하면 C로도 가능하겠지.  13  */  14 #include <iostream>  15 #include <string>  16 #include <queue>  17 #include <stack>  18 using namespace std;  19  20 class modularSe7en{  21 private:  22     int f0_simple_is_good(unsigned int _dividend);  23     int f0_simple_too(unsigned int _dividend);  24     int f1_ancesteral_method(unsigned int _dividend);  25     int f2_Spence_method(unsigned int _dividend);  26     int f3_ThousandOne(unsigned int _dividend);  27     int f4_Lyons_method(unsigned int _dividend);  28     int f5_Toja_method(unsigned int _dividend);  29 public:  30     int doJob(int menu, unsigned int dividend);    // menu: 1~7  31     void doDoDo(unsigned int dividend);            //olleh~  32 };  33  34 int main(){  35     // 4294967295 뒤에 U를 붙였는데, 이는 2^32 - 1 값이다.  36     // 컴파일하면 "warning: this decimal constant is unsigned only in ISO C90"와 같은 메시지가 뜨는데,  37     // 4byte int에 2^31이상의 값을 넣으려는 경우, unsigned가 되어 있더라도 경고 메시지가 나온단다.  38     // 참조 : http://yangseo.tistory.com/entry/warning-this-decimal-constant-is-unsigned-only-in-ISO-C90  39     unsigned int dividend[7] = {1024767, 100101110, 327677, 4294967295U, 16801280, 1152863, 11223346};  40     class modularSe7en mod7;  41     for (int i=0; i<7; i++){  42         mod7.doDoDo(dividend[i]);  43     }  44     return 0;  45 }  46  47 int modularSe7en::doJob(int menu, unsigned int dividend){  48     switch (menu){  49     case 0:  50         return f0_simple_is_good(dividend); break;  51     case 1:  52         return f0_simple_too(dividend); break;  53     case 2:  54         return f1_ancesteral_method(dividend); break;  55     case 3:  56         return f2_Spence_method(dividend); break;  57     case 4:  58         return f3_ThousandOne(dividend); break;  59     case 5:  60         return f4_Lyons_method(dividend); break;  61     case 6:  62         return f5_Toja_method(dividend); break;  63     default:  64         return -1024767; break;  65     }  66 }  67 void modularSe7en::doDoDo(unsigned int dividend){  68     int ret = -2;  69     string messages[7] = {"0. Simple one",  70                           "0. Another simple one",  71                           "1. Ancestor's method",  72                           "2. Spencer's method",  73                           "3. Using 1001",  74                           "4. Lyons's method",  75                           "5. Toja's method"};  76  77     cout << dividend << " modular 7 is" << endl;  78  79     for (int i=0; i<7; i++){  80         cout.width(21); cout.flags(ios::left);  81         cout << messages[i];  82  83         ret = doJob(i, dividend);  84         if (ret != -1)  85             cout << " : " << ret << endl;  86         else cout << " : x" <<  endl;  87     }  88     cout << endl;  89     return;  90 }  91  92  93 int modularSe7en::f0_simple_is_good(unsigned int _dividend){  94     return _dividend % 7;    // 더 이상의 자세한 설명은 생략한다.  95 }  96 int modularSe7en::f0_simple_too(unsigned int _dividend){  97     return _dividend - (_dividend / 7) * 7; // 더이상 설명이 必要韓紙?  98 }  99 int modularSe7en::f1_ancesteral_method(unsigned int _dividend){ 100     // 과거의  방법 101     // 특이한 순서로 된 6개의 숫자가 필요하다. 102     // 일의자리부터 순서대로 곱해서 더해나간다. 103     // ABCDE라면 Ex1 + Dx3 + Cx2 + Bx6 + Ax4 104     // 더한 합이 7의 배수라면 원래 수도 7의 배수 105     int narr[6] = {1, 3, 2, 6, 4, 5}; 106     unsigned int dividend = _dividend; 107 108     queue<int> numberq; 109     int number = -1; 110     int sum = 0; 111 112     // 맨 끝의 자리부터 뽑아서 큐에 넣는다. 113     while (dividend != 0){ 114         number = dividend - (dividend/10)*10; 115         dividend /= 10; 116         numberq.push(number); 117     }; 118 119     // 큐에서 하나씩 뽑아서 위의 배열에 순서대로 곱해서 더한다. 120     for (int i=0; !numberq.empty(); i++){ 121         sum += numberq.front() * narr[i % 6]; 122         numberq.pop(); 123     }; 124 125     return sum % 7; 126 } 127 int modularSe7en::f2_Spence_method(unsigned int _dividend){ 128     // 스펜스의 방법 129     // 나머지를 구하는 것이 아니라, 7의 배수인지만 확인 가능 130     // 나머지가 0이면 7의 배수 131     // 여기서는 7의 배수가 아니면 -1을 반환한다. 132     int number = 0; 133     unsigned int dividend = _dividend; 134 135     // 끝자리를 떼어 두배해서 나머지부분에서 뺀다. 136     // 12345678이면 1234567 - 2 x 8 137     // 계속 반복해서 두자리가 되면 그걸 7로 나눈 나머지가 0이면 7의 배수 138     // 아니면 아님-_- 나머지따윈 알수 업뜸. 139     // 2를 곱해서 빼는 대신 5배해서 더할 수도 있지만, 그러면 수가 계속 커지잖아. 140     while( dividend > 100){ 141         number = dividend - (dividend/10)*10; 142         dividend = (dividend/10) - (2*number); 143     } 144     return (dividend % 7) == 0 ? 0 : -1; 145 } 146 147 int modularSe7en::f3_ThousandOne(unsigned int _dividend){ 148     // 1001이 7의 배수임을 이용하는 방법 149     // 방법이 간단해서 유용함 근데 너무 큰 수면 좀 곤난 150     // 1000배정도씩 줄여나가는 방법 151     unsigned int dividend = _dividend; 152     unsigned int divbyts = dividend; 153     int remainder = 0; 154 155     // 123456 = 123 x 1000 + 456 156     //        = 123 x 1001 - 123 + 456 이므로 157     // -123 + 456의 나머지를 구한다. 158     // 숫자가 큰 경우 -123부분이 클텐데 159     // 이부분의 절대값이 1000보다 작아질 때 까지 반복 160     while (divbyts > 1001){ 161         divbyts = dividend / 1000; 162         remainder = dividend - divbyts * 1000; 163         remainder -= divbyts; 164         while (remainder < 0){ 165             remainder += 1001; 166         } 167         dividend = remainder; 168     } 169     // while (remainder < 0) 부분은 170     // 나머지부분이 0보다 작으면 나머지를 구할 수 없으므로, 171     // dividor인 1001을 더한다. 172     // 여기서는 unsigned된 변수들이므로 양수가 될 때까지 더해준다. 173     // 123100 = 123 x 1000 + 100 174     //           = 123 x 1001 - 123 +100 175     //          = 123 x 1001 - 23 176     //          = 122 x 1001 + 1001 - 23 177     //          = 122 x 1001 + 978 178 179     return remainder % 7; 180 } 181 182 int modularSe7en::f4_Lyons_method(unsigned int _dividend){ 183     // 뉴욕의 신경정신과 의사 라이언스(Vosburgh Lyons)가 발견하였음. 184     // 역시 수학은 정상인의 과학이 아님-_-;; 185     unsigned int dividend = _dividend; 186     unsigned int divbyhud = 0; 187     int remainder = 0; 188     int sumarray[3]={0,0,0}; 189     int left = 0; 190     int right = 0; 191 192     queue<int> numberq; 193     divbyhud = dividend; 194 195     // 뒤에서부터 두자리씩 끊어서 7로 나눈 나머지를 큐에 넣는다. 196     do{ 197         remainder = divbyhud - (divbyhud/100) * 100; 198         divbyhud /= 100; 199         numberq.push(remainder % 7); 200     } while(divbyhud > 0); 201 202     // 큐에서 뽑아서 3으로 나눈 나머지가 같은놈끼리 더함 203     // 3개씩 묶어서 세로로 더하는것 204     for (int i=0; !numberq.empty(); i++){ 205         sumarray[i%3] += numberq.front(); 206         numberq.pop(); 207     } 208 209     //합들을 7로 나눔 210     for (int i=0; i<3; i++){ 211         sumarray[i] %= 7; 212     } 213 214     // A B C 에서(index 2 1 0) 215     // AB BC로 수를 만들어 BC - AB한다. 216     left = (sumarray[2] * 10 + sumarray[1]) % 7; 217     right = (sumarray[1] * 10 + sumarray[0]) % 7; 218 219     return right >= left ? right - left : right - left + 7; 220 } 221 222 int modularSe7en::f5_Toja_method(unsigned int _dividend){ 223     // 브라질 상파울루 대학의 Toja가 고안한 방법 224     // 쌈바스타일임 ㅇㅇ 225     // 역시나 7의 배수인지만 판별 가능. 226 227     unsigned int dividend = _dividend; 228     unsigned int divbyhud = 0; 229     int remainder = 0; 230 231     queue<int> numberQ; 232     stack<int> numberStk; 233 234     do{ 235         //라이언스 판정법과 마찬가지로 두자리씩 끊어서 나머지를 구한다. 236         divbyhud = dividend; 237         do{ 238             remainder = divbyhud - (divbyhud/100) * 100; 239             divbyhud /= 100; 240             numberQ.push(remainder % 7); 241         } while(divbyhud > 0); 242 243 244         // 구한 나머지를, 오른쪽부터 짝수번째의 놈은 7에서 뺀 수로 바꾸고 전체의 순서를 거꾸로 한다. 245         // 2 1 3 5 6 이었으면 246         // 2 6 3 2 6 이 되고, 이걸 거꾸로 써서, 247         // 6 2 3 6 2 가 된다. 248         // 순서를 거꾸로 하기 위해 스택을 사용. 249         int tmp; 250         for (int i=0; !numberQ.empty(); i++){ 251             tmp = numberQ.front(); numberQ.pop(); 252             if (i % 2 == 1) 253                 numberStk.push( 7 - tmp); 254             else numberStk.push(tmp); 255         } 256 257         // 거꾸로 만든 숫자들을 다시 수로 복원 258         dividend = 0; 259         int multiply = 1; 260         while (!numberStk.empty()){ 261             dividend += numberStk.top() * multiply; 262             multiply *= 10; 263             numberStk.pop(); 264         } 265     }while (dividend > 100); //요걸 두자리 수가 될때까지 반복. 266 267     return (dividend % 7) == 0 ? 0 : -1; 268 269 } 270