poj 1047 Round and Round We Go(高精度)

Memory: 160K

Time: 0MS

解题思路

题意：

    循环数是一个n位数，当它分别与1到n相乘时，结果是原来的那个数循环左移或者右移k位。就是当你考虑最后一位数回绕到第一位数时，这个数跟原来一样了。要求是输入一些数，判断是不是循环数。

思路：

   看了description里面的例子，我发现原数乘1.2…..n时，结果是依次递增的（废话是递增的）。

   具体的做法是，用string类的一个对象num[0]存放原数，然后把它循环左移一位放在num[1]中，再把num[1]循环左移一位放在num[2]中，以此类推，最后一个在num[n-1]中。用qsort把num从小到大排序。

    将num[0]的每个字符转换成整型，倒着存在number中，用1到n分别去乘number，结果分别跟num[i]  (i=0..n-1)对照，如果有不同说明不是循环数，否则就是循环数。

源程序

 

#include <stdio.h>
#include <string>
#include <iostream>
#include <conio.h>
#include <stdlib.h>
using namespace std;

#define N 65
int res[N], number[N], a[2];

void multi(int m, int n)
{
    int i, j;

    memset(res, 0, sizeof(res));
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            res[i+j] += a[j] * number[i];
    for(i=0; i<n; i++)
    {
        if(res[i] >= 10)
        {
            res[i+1] += res[i] / 10;
            res[i] = res[i] % 10;
        }
    }
}

int cmp(const void *p, const void *q)
{
    string *a = (string *) p;
    string *b = (string *) q;
    return (*a).compare(*b);
}

int main()
{
    int i, j, k;
    int n, flag;    
    string num[N];
    string str;
    freopen("in.txt", "r", stdin);
    while(cin >> num[0])
    {    
        str = num[0].substr(0);
        n = num[0].size();
        for(i=1; i<=n; i++)
            number[n-i] = num[0].at(i-1) - '0';
        for(i=1; i<n; i++)
        {
            num[i] = num[i-1].substr(1);
            num[i].push_back(num[i-1].at(0));
//            cout << num[i] << endl;

        }
        qsort(num, n, sizeof(num[0]), cmp);
        flag = 0;
        a[0] = a[1] = 0;
        for(i=1; i<=n; i++)
        {
            if(i >= 10)
            {
                a[0] = i % 10;
                a[1] = i / 10;
                k = 2;
            }
            else
            {
                a[0] = i;
                k = 1;
            }
            multi(k, n);
            for(j=0; j<n; j++)
            {
                if(res[j] != num[i-1].at(n-j-1) - '0')
                {
                    flag = 1;
                    break;
                }
            }
            if(flag)
                break;
        }
        cout << str;
        if(flag)
            cout << " is not cyclic" << endl;
        else
            cout << " is cyclic" << endl;
        memset(num, 0, sizeof(num));
    }
    getch();
    return 0;
}