大衍求一术

by admin on 2020年1月23日

     
大衍求意气风发术

Eddy’s digital Roots

Time
Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K
(Java/Others)


Total Submission: 2730 Accepted Submission: 1572

Problem DescriptionThe digital
root of a positive integer is found by summing the digits of the
integer. If the resulting value is a single digit then that digit is the
digital root. If the resulting value contains two or more digits, those
digits are summed and the process is repeated. This is continued as long
as necessary to obtain a single digit.
For example, consider the positive integer 24. Adding the 2 and the 4
yields a value of 6. Since 6 is a single digit, 6 is the digital root of

  1. Now consider the positive integer 39. Adding the 3 and the 9 yields
  2. Since 12 is not a single digit, the process must be repeated. Adding
    the 1 and the 2 yeilds 3, a single digit and also the digital root of
  3. The Eddy’s easy problem is that : give you the n,want you to find the
    n^n’s digital Roots.InputThe
    input file will contain a list of positive integers n, one per line. The
    end of the input will be indicated by an integer value of zero.
    Notice:For each integer in the input n(n<10000).OutputOutput n^n’s digital root on a
    separate line of the output.Sample
    Input
    240Sample
    Output
    44AuthoreddyRecommendJGShining

    #includeint main(){ int n,mul,num,i; scanf(“%d”,&n); while { num=n; n=n%9; mul=1; for(i=1;i<=num;i++) mul=%9; mul=(mul==0?9:mul); printf("%dn",mul); scanf("%d",&n); } return 0;}

解题报告:
代码来自百度查寻,下边是本人的代码,运维后发觉效用太低了,完全能够断定为超时,一再思虑下决定参考代码

图片 1图片 2TLEMyCode

#include<stdio.h>#include<string.h>int sum[40020];int main(){    int  i, j, t, loop, temp, e, flag, len, n;    memset(sum, 0, sizeof;    while(scanf("%d", &n) != EOF && n)    {        flag = 0;        sum[0] = 1;        for(i=n; i>=1; --i)        {            for(j=0, e=0; j<40020; ++j)                {                    temp = sum[j];                    sum[j] = (e + sum[j]*n)%10;                    e = (e + temp*n)/10;                 }        }        for(i=40019; i>=0; --i)   flag += sum[i];        temp = flag;        e = 0;        if(temp >= 10)        while(temp/10 != 0)        {            e += temp%10;            temp = temp/10;            if(temp/10 == 0)            {                e += temp%10;                if(e/10 != 0) {temp = e; e = 0;}                else break;            }         }        else e = temp;        printf("%dn", e);        memset(sum, 0, sizeof;    }    return 0;    }

在看Discuss时,开掘提醒对9的求模!!不解,寻找百度后找注释,都是只开采对9求模的根本字,开采和难点非亲非故系,思忖了会儿,小编大要发掘了难题的运算表明和代码思路的关联:
假使一个数是:A=an x 10^n + a x 10^ + …… + a1 x 10^1 + a0,
依照难点的情致是将A的A次方相乘后将各位的位数相加,相加后推断是还是不是<10,否的话继续将各位的位数相加,如此生生不息直到最后相加的数0<
result
<=9范围内,这里先从相反的自由化酌量(算是事后诸葛武侯吧,但总比没弄理解好),设A的A次方相乘后的值为M,则M和A一样,也得以写成M=bn
x 10^n + b x 10^ + …… + b1 x 10^1 + b0, 也得以这么写:M=bn x +1State of Qatar + b x
-1卡塔尔(قطر‎+1卡塔尔(قطر‎ + …… + b1 x +1 + b0,
即除了个位上的数外其他位数上的数都得以用bn=999…+ 1代表,除去括号得:

M=(bn x 9999…+ bn) + x 999…+b+ b1 x 9 + b1 + b0;

主题素材条件发挥说将各位上的数相加,对于上式来讲即为将各位位数上的数乘上权值后对9的求模再相加(999…都能被9整除),获得的正是M1=bn+
b+…+b1+b0(先不用想着将这一批数按十进制实行相加,应想着这个数都是求模后剩下来的,等下只怕讲求模的),相加的数M1假设>=10,根据标题条件的野趣又会一而再循环相加,直至获得的Mn<10
那时Mn就为result                  ——上边所说的都感到了求证难点这样叙述是为着对9求模而通过得到余数

归来最先的M,
M是由A个A相乘后的结果,当时须驾驭那样的二个架子:mod能够写成*%x,而M=A*A,
再结合代码就可以预知清楚为何有n个n%9相乘再求模了(n%9到手的数总令人认为是A个位上的数!!而实际上不是)

运用数组准确计算M/N(0<M<N<=100卡塔尔国的值。假使M/N是特别循环小数,则总括并出口它的率先循环节,同一时候要求输出
循环节的起止地点(小数位的序号卡塔尔(قطر‎

大衍求生龙活虎术口诀:

*问题浅析与算法设计
由于计算机字长的范围,常规的浮点运算都有精度约束,为了获取高精度的乘除结果,就必须自行设计达成方式。
为了达成高精度的乘除,可将商存放在大器晚成维数组中,数组的种种成分寄存一人十进制数,即商的率先位存放在率先个要素中,商的第几个人存放在第1个成分中….,依次类推。那样就足以行使数组不代表二个高精度的测度结果。
展解雇法运算时能够有样学样人的手工业操作,即每一趟求出商的第二个人后,将余数乘以10,再总结商的下一人,重复以上进程,当某次总计后的余数为0
时,表示M/N为有限不循环小数某次总计后的余数与近日的某部余数相同期,则M/N为特别循环小数,从该余数第3回面世之后所求得的诸位数正是小数的循环节。
程序具体落到实处时,选用了数组和其它一些技巧来保存除法运算所拿到的余数和商的诸位数。

四人同行七十稀,五数红绿梅八十朝气蓬勃,七子团圆正半月,除百零五便搜查捕获。隐含的算法内容是:对二个正整数,先用3去除所收获的余数与70相乘,再用5去除所拿到的余数与21相乘,最终用7去除所获得余数与15相乘,多少个积相加,并持续用105去减,直到差小于105,就获取最小正整数解。

*程序表达与注释
#include<stdio.h>
int remainder[101],quotient[101]; /*remainder:存放除法的余数;
quotient:依次寄存商的每一人*/
int main()
{
int m,n,i,j;
printf(“Please input a fraction(m/n)(<0<m<n<=100):”);
scanf(“%d/%d”,&m,&n); /*输入被除数和除数*/
printf(“%d/%d it’s accuracy value is:0.”,m,n);
for(i=1;i<=100;i++) /*i: 商的位数*/
{
remainder[m]=i; /*m:除的余数 remainder[m]:该余数对应的商的位数*/
m*=10; /*余数扩充11个人*/
quotient=m/n; /商*/
m=m%n; /*求余数*/
if(m==0) /*余数为0 则意味着是有限小数*/
{
for(j=1;j<=1;j++) printf(“%d”,quotient[j]); /*输出商*/
break; /*退出循环*/
}
if(remainder[m]!=0) /*若该余数对应的位在前头早已冒出过*/
{
for(j=1;j<=i;j++) printf(“%d”,quotient[j]); /*则输出循环小数*/
printf(“ntand it is a infinite cyclic fraction from
%dn”,remainder[m]);
printf(“tdigit to %d digit after decimal point.n”,i);
/*出口循环节的地点*/
break; /*退出*/
}
}
}
*

        
代码:

*思考题
选择数组完毕总计MXN的正确值

        
#include<stdio.h>

 

int remainder(int i);

 

main()

{

         int i;

 

         for
(i=1;i<100;i++)

        
{

                  
if((i-1)%2==0)

                           
printf(“n”);

                  
remainder(i);

        
}

        
getch();

}

 

int remainder (int n)

{

         int
r3,r5,r7,mul,sub,div;

 

        
r3=n%3;

        
r5=n%5;

        
r7=n%7;

 

        
mul=r3*70+r5*21+r7*15;

        
div=mul/105;

        
sub=mul-div*105;

 

        
printf(” %d:%d*70+%d*21+%d*15-%d*105=%d
“,n,r3,r5,r7,div,sub);

 

         return
1;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图