杭电OJ第11页2050~2054算法题（C语言）

2050.折线分割平面

Problem Description
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面
的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下
所示。
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数 n(0<n<=10000),表示折线的数量。
Output
对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。
Sample Input 2 1 2 Sample Output 2 7 

分析： 背景知识：由最初的直线分平面可知，交点的个数决定了射线和线段的条数，进而决定了新增的区域数。同理当用折线分割平面时，折线之间的交点越多，所分割的平面数也就越多。 解决思路：一般来说，直接计算n条折线可分割的最大平面数比较困难，此时可以考虑从最简单的情况入手（例如n=1、n=2、…，进而找出规律），也可以尝试找出n条折线与n-1条折线可分割的最大平面数之间的递推关系。 推导递推式：设fold[i]表示i条折线可分割的最大平面数，则fold[1]=2，那么有n-1条折线时，可分割的最大平面数为fold[n-1]。为了使分割的平面数最多，第n条折线两边的线段要和原来的n-1条折线的边，即2*(n-1)条线段相交，那么易知新增的交点数为4*(n-1)+1（包括第n条折线本身的顶点），又通过分析可知，新增的交点数即为新增的平面数，所以得到如下的递推式： fold[n]=fold[n-1]+4(n-1)+1=fold[n-2]+4(n-2)+4(n-1)+2=…=fold[1]+4+4*2+…+4(n-1)+(n-1)=2n2-n+1

#include  void FoldLine(){ int n,line; scanf("%d",&n); while(n--){ scanf("%d",&line); if(line<=0 || line>10000){ printf("折线数量的取值范围为(0,10000]之间的整数！\n"); continue; } printf("%d\n",2*line*line-line+1); } } 

2051.Bitset

Problem Description
Give you a number on base ten,you should output it on base two.(0 < n < 1000) Input
For each case there is a postive number n on base ten, end of file. Output
For each case output a number on base two. Sample Input 1 2 3 Sample Output 1 10 11 

分析：本题与2031进制转换较为类似，且更为简单，只需要将输入的十进制转换为二进制即可。

#include  void TenToTwo(){ int n,two[11],i,j; while(scanf("%d",&n)!=EOF){ if(n<=0 || n>=1000) { printf("n的取值范围为(0,1000)之间的整数！\n"); continue; } i=0; while(n>0){ two[i]=n%2; n/=2; i++; } for(j=i-1;j>=0;j--){ printf("%d",two[j]); } printf("\n"); } } 

2052.Picture

Problem Description
Give you the width and height of the rectangle,darw it. Input
Input contains a number of test cases.For each case ,there are two numbers 
n and m (0 < n,m < 75)indicate the width and height of the rectangle.Iuput 
ends of EOF. Output
For each case,you should draw a rectangle with the width and height giving 
in the input. after each case, you should a blank line. Sample Input 3 2 Sample Output +---+ | | | | +---+ 

分析：按照题目要求画出矩阵即可。

#include  void DrawLine(int n){ int i; printf("+"); for(i=0;i<n;i++){ printf("-"); } printf("+\n\n"); } void DarwRectangle(){ int n,m,i,j; while(scanf("%d%d",&n,&m)!=EOF){ if(n<=0 || n>=75 || m<=0 || m>=75){ printf("长和宽的取值范围均为(0,75)之间的整数！\n"); continue; } DrawLine(n); for(i=0;i<m;i++){ printf("|"); for(j=0;j<n;j++){ printf(" "); } printf("|\n\n"); } DrawLine(n); printf("\n"); } } 

2053.Switch Game

Problem Description
There are many lamps in a line. All of them are off at first. A series of 
operations are carried out on these lamps. On the i-th operation, the 
lamps whose numbers are the multiple of i change the condition ( on to off 
and off to on ). Input
Each test case contains only a number n ( 0< n<= 10^5) in a line. Output
Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ). Sample Input 1 5 Sample Output 1 0 Hint
Consider the second test case: The initial condition : 0 0 0 0 0 …
After the first operation : 1 1 1 1 1 …
After the second operation : 1 0 1 0 1 …
After the third operation : 1 0 0 0 1 …
After the fourth operation : 1 0 0 1 1 …
After the fifth operation : 1 0 0 1 0 …

The later operations cannot change the condition of the fifth lamp any more. So the answer is 0. 

分析：在1~n次的操作中，若n是i的倍数，则count++(初值为0)，在第n次操作结束后，在用count对2取余，其结果即为第n个指示灯的状态。

#include  void SwitchGame(){ int i,n,count; while(scanf("%d",&n)!=EOF){ count=0; for(i=1;i<=n;i++){ if(n%i==0){ count++; } } printf("%d\n",count%2); } } 

2054.A == B ?

Problem Description
Give you two numbers A and B, if A is equal to B, you should print "YES", or print "NO". Input
each test case contains two numbers A and B. Output for each case, if A is equal to B, you should print "YES", or print "NO". Sample Input 1 2 2 2 3 3 4 3 Sample Output
NO
YES
YES
NO

分析：本题看似简单，实际上需要考虑输入的格式不同，例如输入的004和4.0，需要做统一的处理后再进行比较。

#include  #include  //将输入的数字看成字符串作统一的处理，然后再比较 void StrUnify(char str[]){ int length=strlen(str),c,i; //检测有无小数点，若没有则在末尾补小数点 for(i=0;i<length;i++){ if(str[i]=='.') break; if(i==length-1){ str[length]='.'; str[length+1]='\0'; break; } } //判断符号  if(str[0]=='+' || str[0]=='-'){ length=1; }else { length=0; } //首部去0  while(str[length]=='0'){ c=length; if(str[length+1]=='.') break; while(1) { str[c]=str[c+1]; if(str[c+1]=='\0') break; c++; } } //尾部去0 length=strlen(str); while(str[length-1]=='0') { str[length-1]=str[length]; length--; } } void EqualNum(){ char a[10000],b[10000]; long n,m,c; while(scanf("%s %s",a,b)!=EOF) { StrUnify(a); StrUnify(b); if(a[0]=='-' && (b[0]=='+'||b[0]>='0')){ printf("NO\n"); continue; } if(b[0]=='-' && (a[0]=='+'||a[0]>='0')){ printf("NO\n"); continue; } n=m=0; if(a[0]=='+'||a[0]=='-') n++; if(b[0]=='+'||b[0]=='-') m++; c=0; while(a[n]!='\0' || b[m]!='\0'){ if(a[n]!=b[m]){ c++; break; } n++; m++; } if(c==0){ printf("YES\n"); }else{ printf("NO\n"); } } } 

杭电OJ第11页2055~2059算法题（C语言）