ACM初步-简单数据处理问题

ACM初步

---第二讲简单数据处理问题计算机科学与工程学院开胃羹1、integer整数2、positive正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的ACM数学题特点分析:题意容易理解算法相对简单（有些很难的！！）编程比较容易ACM/ICPC入门练习的好选择下面，分类介绍：最大公约数、最小公倍数(hdoj_1108、1019)gcd(a,b)=gcd(a,bmoda)gcd(a1,a2,a3)=gcd(gcd(a1,a2),a3)gcd(a1,a2,a3,a4)=gcd(gcd(a1,a2,a3),a4)lcm(a,b)=a*b/gcd(a,b)1008:Elevator电梯问题：Hdoj-1008问题描述

在城市的高层建筑物中只有一部电梯，由N个正整数组成一个请求列表，列表中的数字表示电梯将在哪层停，电梯按列表顺序依次停靠。电梯每上行一层需要花6秒时间，每下行一层需要花4秒时间，电梯每停一次需要用时5秒。对于给定的请求列表，计算完成所有请求需要花费的时间，电梯从第0层开始，完成所有请求后又回到第0层。输入

输入包括多组测试数据，每组测试数据占一行，其中第一个正整数N，表示该请求列表中有N个数据，接下来是N个整数；如果N=0，则表示输入结束。输出

对每组测试数据，输出完成列表所有请求的总时间，每个结果占一行。#include<stdio.h>intmain(){ inti,n,tm,from,to;

while(1) { scanf("%d",&n); if(n==0)break; tm=0; from=0; for(i=0;i<n;i++) { scanf("%d",&to); if(from<to)tm+=(to-from)*6+5; elsetm+=(from-to)*4+5; from=to; } printf("%d\n",tm); }

return0; }发工资咯Hdoj_2021/showproblem.php?pid=2021#include<stdio.h>intmain(){ intn,m,count,c100,c50,c10,c5,c2,c1; while(1) { scanf("%d",&n); if(n==0)break; count=0; for(;n>0;n--) { scanf("%d",&m); c100=m/100; c50=m%100/50; c10=m%100%50/10; c5=m%100%50%10/5; c2=m%100%50%10%5/2; c1=m%100%50%10%5%2; count+=c100+c50+c10+c5+c2+c1; } printf("%d\n",count); } return0;}数根：Hdoj-1013问题描述：一个正整数的数根可以这样求得：计算该整数的各位数字之和，如果结果值是单个数字的数，那么这个数就是所求数根；如果结果值是由两位或两位以上的数字组成的数，则继续计算各位数字的和，直到结果值只有一位数字为止。 例如：正整数24,2+4=6，则6为24的根。 又如：正整数39,3+9=12，由于12不是单个数字组成的数，所以继续计算，1+2=3，所以39的根为3.输入：输入包括多组测试数据，每组测试数据包括一个正整数，并且占一行，输入数据为0时，表示输入结束。输出：对于每组测试数据，给出对应输出，并且每组输出占一行。#include<stdio.h>intmain(){ longsum,n; while(1) { scanf("%ld",&n);

if(n==0)break; do{ sum=0; while(n>0) { sum+=n%10; n/=10; } n=sum; }while(n>=10); printf("%ld\n",sum); } return0; }数根：Hdoj-1018问题描述：大数的位数 在很多应用中会涉及大数的位数问题，例如在数据传输、密码等应用中。现在给出一个整数，你来确定这个数的阶乘的位数。输入： 输入包含多行数据，第一行为整数n，表示共有n组测试数据，接下来的n行中，每行为一个大于等于1并且小于等于pow(10,7)的整数。

输出： 对应每个输入数据输出一个结果，并且每个结果占一行。输入样例：

2 10 20

输出样例：

7 19问题分析：数学知识：一个数N，取其以10为底的对数并取整，得到的值为整数N的位长减1。

n!=1*2*...*n log10(n!)=log10(1)+log10(2)+...+log10(n)#include<stdio.h>#include<math.h>intmain(){ longn,i,m; doublesum;

while(scanf("%d",&n)!=EOF) { for(;n>0;n--) { scanf("%ld",&m); sum=1.0; for(i=1;i<=m;i++)sum+=log10(i); printf("%ld\n",(long)sum); } }

return0;}问题描述：路边的树 长度为L的路边有一排树，相邻树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0,1,2，...，L，都种有一棵树。 现在马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。 已知有M个区域需要修建地铁，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。输入： 输入包含多组测试数据，每组测试数据的第一行有两个整数L（1<=L<=10000）和M（1<=M<=100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行，每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出： 对于每组测试数据，输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。输入样例：

5003 150300 100200 470471输出样例：

298问题描述：会绕圈的数

任意一个正整数，把它的每一位数字都平方后相加得到一个数；将这个数的每一位数字再平方相加；依次进行就会产生循环现象。例如：1234。

1^2+2^2+3^2+4^2=1+4+9+16=30 3^2+0^2=9+0=9 9^2=81 8^2+1^2=64+1=65 6^2+5^2=36+25=61 6^2+1^2=36+1=37 3^2+7^2=9+49=58 5^2+8^2=25+64=89 8^2+9^2=64+81=145 1^2+4^2+5^2=1+16+25=42 4^2+2^2=16+4=20 2^2+0^2=4+0=4 4^2=16 1^2+6^2=1+36=37

由于前面已经出现过37，这时就产生了循环。设计一个程序，对给定的一个数，打印出到出现循环为止的所有数。输入： 输入包括多组测试数据，每组测试数据占一行并且只有一个正整数m（m<10,000,000），当m=0时表示输入结束。输出： 对每组测试数字输出一行结果，结果中包括到第一次产生循环时的所有整数。输入样例：

1234 0输出样例：

1234309816561375889145422041637问题分析： 两个关键问题： （1）对一个整数求其各位数字的平方和； （2）在已经产生的结果中查找当前值是否已经出现过。问题描述：竞赛排名

4名同学同时参加了竞赛，公布成绩后发现4名同学的成绩彼此互不相同。 甲说：我成绩最好，乙成绩最差，丙排第三。 乙说：我成绩最好，甲成绩最差，丙排第二，丁排第三。