最小生成数

code

4 年前

最小生成数

时间： 10ms 内存：128M

描述：

小R特别喜欢数字，经常玩一些数字游戏，有一天他发现一个有趣的规律，他发现某些数字可以由另一个数字通过加上本身的数位和的得出，比如256=245+2+4+5。小R对此很感兴趣，于是他将245称为256的生成数，但是很快他就发现不是所有数字都有这种规律的，有些数字没有其他数字可以生成(比如3),而有些数字可以由多个数字生成(216=198+1+9+8=207+2+0+7)，小R因此很苦恼，他想找出任意数字的最小生成数，但是单纯依靠人工太难了，你能通过编程帮帮他吗？

输入：

输入包含T组测试数据，第一行输入T，接下来T行每行输入一个N（0<=N<=100000）。

输出：

对于每个正整数N，每行输出所对应的最小生成数，没有最小生成数输出0。

示例输入：

示例输出：

198
0
1979

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
bool shu(int t,int j)
{
    int a,b,c,d,e,f;
    a = t % 10;
    b = t / 10  % 10;
    c = t / 100 % 10;
    d = t / 1000 % 10;
    e = t / 10000 % 10;
    f = t / 100000 % 10;
    if(a+b+c+d+e+f+t == j){
        return true;
    }
    else
        return false;
}
int main()
{
    int i,j,k,z = 0;
    scanf("%d",&k);
    for(int x = 0;x<k;x++){
        scanf("%d",&j);
        z = 0;
        for(i = 3;i<j+1;i++){
            if(shu(i,j)){
                printf("%d\n",i);
                z = 1;
                break;
            }
        }
        if(z == 0){
                printf("0\n");
            }
    }
    return 0;
}

参考答案（时间最优[12]）：

#include <stdio.h>
#include <stdlib.h>

int main()
{
   int n;
   scanf("%d",&n);
   while(n)
   {
       n--;
       int m,sum,i,a=0,b,c;
       scanf("%d",&m);
       if(m-55<0)
        b=2;
       else b=m-55;
       for(i=b;i<m;i++)
       {
           c=i;sum=0;a=0;
           while(c>0)
           {sum=sum+c%10;
           c=c/10;}
           if(i+sum==m)
           {
               a=1;
               printf("%d\n",i);
               break;
           }
       }
       if(a==0)
        printf("0\n");
   }
   return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。