ACM程序设计算法原理和ACM入门PPT.ppt

Output For each test case, you should output the rightmost digit of N^N. ?Sample Input 2 3 4 ?Sample Output 7 6 Hint In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6. 直接做 int i,n,tmp,sum; cinn; while(n--) { sum=1; cini; tmp=i%10; for(int j=1;j=i;j++) { sum=sum*tmp; sum=sum%10; } sum=sum%10; coutsumendl; } Time Limit Exceeded 时间超时了！ 就不是直接做的题！ 先找规律 0 1 5 6 这4个数好啊 周期=1 4：4 6 周期=2 9：9 1 2：2 4 8 6 周期=4 3: 3 9 7 1 7: 7 9 3 1 8: 8 4 2 6 int n; int a[10][4] = { {0},{1},{6,2,4,8},{1,3,9,7},{6,4},{5},{6},{1,7,9,3},{6,8,4,2},{1,9} },d,num; scanf(%d,num); while(num--) { scanf(%ld,n); d = n % 10; if(d == 0||d == 1||d == 5||d == 6) printf(%d\n,d); else if(d == 4||d == 9) printf(%d\n,a[d][n % 2]); else if(d == 2||d == 3||d == 7||d == 8) printf(%d\n,a[d][n % 4]); } 数的长度 (nefu_oj 65) N! (N的阶乘) 是非常大的数，计算公式为：N! = N * (N - 1) * (N - 2) * ... * 2 * 1)。现在需要知道N!有多少（十进制）位。 每行输入1个正整数N。0 N 1000000 对于每个N，输出N!的（十进制）位数。 1 3 32000 1000000 1 1 130271 5565709 1 3 32000 1000000 如何计算？ 所谓N!的（十进制）位数，就是Lg(N!)+1，根据数学公式，有 N!=1*2*……*N Lg(N!)=lg(2)+……+lg(N) 图 T(n)与规模n的函数关系 Temp=i；i=j；j=temp； 以上三条单个语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=Ο(1)。 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是Ο(1)。 【例1】交换i和j的内容。 【例2】变量计数之一。 (1) x=0；=0； (2) for(k-1；=n；++) (3) x++； (4) for(i=1；=n；++) (5) for(j=1；j=n；++) (6) y++； 该算法段的时间复杂度为T(n)=Ο(n2)。 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 【例3】变量计数之二 (1) x=1； (2) for(i=1；i=n；i++) (3) for(j=1；j=i；j++) (4) for(k=1；k=j；k++) (5) x++； 该算法段中频度最大的语句是(5)，从内层循环向外层分析语句(5)的执行次数： 复杂度：O(n3) 算法的描述方法 ⑴ 自然语言 优点：容易理解 缺点：冗长、二义性 使用方法：粗线条描述算法思想 注意事项：避免写成自然段 ① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束； 否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新