杭电oj基础题目（1106、1108、1163、1164、1170、1194、1197）

1106、排序

输入一行数字，如果我们把这行数字中的‘5’都看成空格，那么就得到一行用空格分割的若干非负整数（可能有些整数以‘0’开头，这些头部的‘0’应该被忽略掉，除非这个整数就是由若干个‘0’组成的，这时这个整数就是0）。
你的任务是：对这些分割得到的整数，依从小到大的顺序排序输出。
Input
输入包含多组测试用例，每组输入数据只有一行数字（数字之间没有空格），这行数字的长度不大于1000。
输入数据保证：分割得到的非负整数不会大于100000000；输入数据不可能全由‘5’组成。
Output
对于每个测试用例，输出分割得到的整数排序的结果，相邻的两个整数之间用一个空格分开，每组输出占一行。
Sample input

0051231232050775

Sample Output

0 77 12312320

Code
1、排序可以利用快速排序算法
2、使用字符数组存储输入的一行数字字符串

#include<iostream>
#include<string.h>
using namespace std;
void QuickSort(int R[],int low,int high){
    int pivot,i,j;i=low,j=high;if(i<j){
    pivot=R[i];while(i!=j){
    while(j>i&&R[j]>pivot)j--;if(j>i){
    R[i]=R[j];i++;}while(i<j&&R[i]<pivot)i++;if(i<j){
    R[j]=R[i];j--;}}R[i]=pivot;QuickSort(R,low,i-1);QuickSort(R,i+1,high);}
}
int main(){
    char c[1000];//用来存放输入的一行数字while(cin>>c){
    int len=strlen(c);int num[1000],t[1000];//对数组num[] 进行初始化 for(int i=0;i<1000;i++){
    num[i]=0;}int j=0,k=0;bool flag=false;for(int i=0;i<len;i++){
    if(c[i]!='5'){
    t[j++]=c[i]-'0';flag=true;//将字符转化为整数 if(i==len-1){
     //输入的数字不是以5结束的 for(int m=0;m<j;m++){
    num[k]=num[k]*10+t[m];}k++;    }}else{
    if(flag==false) continue;for(int m=0;m<j;m++){
    num[k]=num[k]*10+t[m]; //将单独的数字转化为一个十进制的数flag=false; } if(flag==false){
    //对于输入类似115555这样的数据 k++; j=0;}}}//对num[] 数组进行排序，利用快速排序算法 QuickSort(num,0,k-1); for(int i=0;i<k;i++){
    cout<<num[i]<<" ";} cout<<endl;} 

1108、最小公倍数

给定两个正整数，计算这两个正整数的最小公倍数

//给定两个正整数，计算这两个正整数的最小公倍数
#include<iostream>
using namespace std;int f(int a,int b){
    int temp,c,t;c=a*b;if(a<b){
    temp=a;a=b;b=temp;}t=a%b;while(t!=0){
    a=b;b=t;t=a%b;}return c/b;
}
int main(){
    int a,b;//输入的两个正整数范围[1,1000] while(cin>>a>>b){
    cout<<f(a,b)<<endl;}
} 

1157、Who’s in the middle

很简单的一个排序

//对奇数个数的数组进行排序，输出中间数 
#include<iostream>
#include<algorithm>
using namespace std;
int num[10000];
int main(){
    int n;//n[1,10000]且为奇数 while(cin>>n){
    for(int i=0;i<n;i++){
    cin>>num[i];}sort(num,num+n);cout<<num[n/2]<<endl;}    return 0;
}

1163、Eddy’s digital Roots[数字根]

The 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 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. 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 39.
The Eddy’s easy problem is that : give you the n,want you to find the n^n’s digital Roots.
Input
The 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).
Output
Output n^n’s digital root on a separate line of the output.
Sample Input

2
4
0

Sample Output

4
4

思路1：分别计算n个数字的数字根的乘积，
即如3³的数字根:3的数字根3,3乘3得9,9的数字根为9,93=27,27的数字根为9，故3³数字根为9
思路2：利用九余数定理：一个数的各位数字之和相加得到的小于10的数字称为这个数的九余数
因此，只要计算得出nⁿ的九余数,即可求得其数字根
(nⁿ)%9=(n%9n%9…n%9)%9
方法一：
余数定理

/* 计算n^n的数字根，直接计算n^n会超时 思路1：分别计算n个数字的数字根的乘积， 即如3^3的数字根:3的数字根3,3乘3得9,9的数字根为9,9*3=27,27的数字根为9，故3^3数字根为9 思路2：利用九余数定理：一个数的各位数字之和相加得到的小于10的数字称为这个数的九余数 因此，只要计算得出n^n的九余数,即可求得其数字根 (n^n)%9=(n%9*n%9......n%9)%9 */ 
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    if(n==0) break;//n^n的数字根int root=1;for(int i=0;i<n;i++){
    root=root*n%9;}root=root%9;if(root==0){
    cout<<9<<endl;}elsecout<<root<<endl;}return 0;
} 

方法二：
nⁿ的数字根可以计算这n个数字的数字根的乘积

//n^n的数字根
#include<iostream>
using namespace std;
int main(){
    int n;//n[1,10000]while(cin>>n){
    if(n==0) return 0;//计算n的数字根 int root=n,t,num;t=n;while(root>=10){
    //n大于10 t=root;root=0;int l;while(t!=0){
    l=t%10;root=root+l;t=t/10;} }//遍历 for(int i=0;i<n-1;i++){
    num=root*n;root=num;int p;//计算num的数字根 while(root>=10){
    num=root;root=0;while(num!=0){
    p=num%10;root=root+p;num=num/10;}} }cout<<root<<endl;}
} //另外简单的一种写法
/* 计算n^n的数字根，直接计算n^n会超时 思路1：分别计算n个数字的数字根的乘积， 即如3^3的数字根:3的数字根3,3乘3得9,9的数字根为9,9*3=27,27的数字根为9，故3^3数字根为9 */ 
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    if(n==0) break;//n^n的数字根int root=1,sum;for(int i=0;i<n;i++){
    root=root*n;//计算root的数字根 //计算root的各位数字之和while(root/10>0){
    sum=0;while(root>0){
    int t=root%10;sum=sum+t;root=root/10;}root=sum;}} cout<<root<<endl;}return 0;
} 

1164、Eddy’s research I[将一个数拆分成素数的乘积]

Eddy’s interest is very extensive, recently he is interested in prime number. Eddy discover the all number owned can be divided into the multiply of prime number, but he can’t write program, so Eddy has to ask intelligent you to help him, he asks you to write a program which can do the number to divided into the multiply of prime number factor .
Input
The input will contain a number 1 < x<= 65535 per line representing the number of elements of the set.
Output
You have to print a line in the output for each entry with the answer to the previous question.
Sample Input

11
9412

Sample Output

11
2*2*13*181

Code:
1、判断一个数是否是素数
2、以12为例：找到12的第一个素因数2,12/2=6，找6的第一个素因数2,6/2=3,找3的第一个素因数3,3/3=1结束

//将一个数拆分成素数的乘积
#include<iostream>
using namespace std;
//判断一个数是否是素数
//以12为例：找到12的第一个素因数2,12/2=6，找6的第一个素因数2,6/2=3,找3的第一个素因数3,3/3=1结束
//12=2*2*3 
bool isPrime(int n){
    for(int i=2;i<=n/2;i++){
    if(n%i==0)return 0;}return 1;
} 
int main(){
    int n;//n(1.65535]while(cin>>n){
    for(int i=2;i<=n;i++){
    if(n%i==0&&isPrime(i)==1){
    if(n/i==1){
    cout<<i<<endl;break;}cout<<i<<"*";n=n/i;i=1;}}    }
} 

1170、Balloon Comes![已知操作符和操作数，计算相应结果]

The contest starts now! How excited it is to see balloons floating around. You, one of the best programmers in HDU, can get a very beautiful balloon if only you have solved the very very very… easy problem.
Give you an operator (+,-,, / --denoting addition, subtraction, multiplication, division respectively) and two positive integers, your task is to output the result.
Is it very easy?
Come on, guy! PLMM will send you a beautiful Balloon right now!
Good Luck!
Input
Input contains multiple test cases. The first line of the input is a single integer T (0<T<1000) which is the number of test cases. T test cases follow. Each test case contains a char C (+,-,, /) and two integers A and B(0<A,B<10000).Of course, we all know that A and B are operands and C is an operator.
Output
For each case, print the operation result. The result should be rounded to 2 decimal places If and only if it is not an integer.
Sample Input

4
+ 1 2
- 1 2
* 1 2
/ 1 2

Sample Output

3
-1
2
0.50

Code:
1、数的计算
2、注意输出要求

//已知操作符和操作数，计算相应结果
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int t;//t(0,1000)while(cin>>t){
    char c;//操作符long long a,b,result; //a,b(0,10000)double result1;for(int i=0;i<t;i++){
    cin>>c>>a>>b;switch(c){
    case '+':result=a+b;cout<<result<<endl;break;case '-':result=a-b;cout<<result<<endl;break;case '*':result=a*b;cout<<result<<endl;break;case '/':result1=double(a)/double(b);cout<<setiosflags(ios::fixed);if(a%b==0){
    cout<<setprecision(0)<<result1<<endl;}    else{
    cout<<setprecision(2)<<result1<<endl;}break; }}}
} 

1194、Beat the Spread![给出两个数的和以及两个数的差，求这两个数–二元一次方程]

Superbowl Sunday is nearly here. In order to pass the time waiting for the half-time commercials and wardrobe malfunctions, the local hackers have organized a betting pool on the game. Members place their bets on the sum of the two final scores, or on the absolute difference between the two scores.

Given the winning numbers for each type of bet, can you deduce the final scores?
Input
The first line of input contains n, the number of test cases. n lines follow, each representing a test case. Each test case gives s and d, non-negative integers representing the sum and (absolute) difference between the two final scores.
Output
For each test case, output a line giving the two final scores, largest first. If there are no such scores, output a line containing “impossible”. Recall that football scores are always non-negative integers.
Sample Intput

2
40 20
20 40

Sample Output

30 10
impossible

Code:
1、解二元一次方程
2、注意题目中限制条件

//给出两个数的和以及两个数的差，求这两个数 
//解二元一次方程组 
#include<iostream>
using namespace std;
int main(){
    int n;while(cin>>n){
    int a,b,x,y;for(int i=0;i<n;i++){
    cin>>a>>b;if(a-b>0){
    x=a+b;y=a-b;if(x%2==0&&y%2==0){
    cout<<x/2<<" "<<y/2<<endl;}else{
    cout<<"impossible"<<endl;}}else{
    cout<<"impossible"<<endl;}}}
} 

1196、Lowest Bit[找出一个正整数的二进制的最低位]

Given an positive integer A (1 <= A <= 100), output the lowest bit of A.

For example, given A = 26, we can write A in binary form as 11010, so the lowest bit of A is 10, so the output should be 2.

Another example goes like this: given A = 88, we can write A in binary form as 1011000, so the lowest bit of A is 1000, so the output should be 8.
Input
Each line of input contains only an integer A (1 <= A <= 100). A line containing “0” indicates the end of input, and this line is not a part of the input data.
Output
For each A in the input, output a line containing only its lowest bit.
Sample Input

26
88
0

Sample Output

2
8

Code:
1、将一个正整数转化为二进制数，找出其最低位，再将其最低位转化为十进制数输出
2、十进制转化为二进制，对2取余

//将一个正整数转化为二进制数，找出其最低位，再将其最低位转化为十进制数输出
#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int a;//输入待处理的数a[1,100]while(cin>>a){
    int num[8],i=0,result;//存放二进制数 if(a==0) return 0;//将a转化为二进制数while(a!=0){
    num[i]=a%2;if(num[i]!=0){
    result=num[i]*pow(2,i);break;}a=a/2;i++;} cout<<result<<endl;} 
} 

1197、Specialized Four-Digit Numbers[输出十进制、十二进制、十六进制各位数之和相等的四位数]

Find and list all four-digit numbers in decimal notation that have the property that the sum of its four digits equals the sum of its digits when represented in hexadecimal (base 16) notation and also equals the sum of its digits when represented in duodecimal (base 12) notation.

For example, the number 2991 has the sum of (decimal) digits 2+9+9+1 = 21. Since 2991 = 11728 + 8144 + 9*12 + 3, its duodecimal representation is 1893(12), and these digits also sum up to 21. But in hexadecimal 2991 is BAF16, and 11+10+15 = 36, so 2991 should be rejected by your program.

The next number (2992), however, has digits that sum to 22 in all three representations (including BB016), so 2992 should be on the listed output. (We don’t want decimal numbers with fewer than four digits - excluding leading zeroes - so that 2992 is the first correct answer.)
Input
There is no input for this problem.
Output
Your output is to be 2992 and all larger four-digit numbers that satisfy the requirements (in strictly increasing order), each on a separate line with no leading or trailing blanks, ending with a new-line character. There are to be no blank lines in the output. The first few lines of the output are shown below.
Sample Input

There is no input for this problem.

Sample Output

2992
2993
2994
2995
2996
2997
2998
2999

Code:
1、给四位数的十进制数，转化为十进制、十二进制、十六进制，且其各位数字相加之和相等的数
2、十进制转化为其他进制数——取余

//任给以四位数的十进制数，输出其十进制、十二进制、十六进制各位数字相加之和相等的数
#include<iostream>
using namespace std;
int main(){
    for(int i=2992;i<10000l;i++){
    //计算十进制的各位数字之和int n=i,t1,sum1=0;while(n!=0){
    t1=n%10;sum1=sum1+t1;n=n/10;} //计算十二进制的各位数字之和int m=i,t2,sum2=0;while(m!=0){
    t2=m%12;sum2=sum2+t2;m=m/12;} //计算十六进制的各位数字之和int s=i,t3,sum3=0;while(s!=0){
    t3=s%16;sum3=sum3+t3;s=s/16;}if(sum1==sum2&&sum2==sum3){
    cout<<i<<endl;}}
}