1.百鸡问题扩展-N鸡问题
问题描述
N元钱买N只鸡，公鸡每只5元，母鸡每只3元，小鸡1元3只，N元钱必须刚好买N只鸡，而且鸡必须整只买，不能劈开买。
有几种买法呢？这就是N鸡问题。
输入在一行中输入一个正整数N。（N<500）
输出在一行中输出两个整数c s，中间用一个空格隔开，表示N元钱买N只鸡共有 c 种买法，且所有买法的公鸡数量之和是 s。如果无解，则 s 为 -1.
输入样例1:
100
输出样例1:
4 24
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
//定义公鸡，母鸡，小鸡数量
int x,y,z;
int w[]=new int[n/5];
int count=0;
int temp=0;
for(x=0;x<=n/5;x++) {
for(y=0;y<=n/3;y++) {
z=n-x-y;
if((z%3==0)&&(5*x+3*y+z/3==n)) {
//System.out.println("公鸡数量"+x+",母鸡数量"+y+",小鸡数量"+z);
temp+=x;
count++;
}
}
}
if(count==0) {
temp=-1;
System.out.println(count+" "+temp);
}else {
System.out.println(count+" "+temp);
}
}
}
2.统计数字问题
问题描述
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。数字计数问题要求对给定书的总页码n(<=200000)，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。
输入只有1行，给出表示书的总页码整数n。
输出共有10行，在第k行输出页码中用到的数字k-1的次数，k=1，2，3，…，10
输入样例:
输入示例。例如：
11
输出样例:
输出示例。例如：
1
4
1
1
1
1
1
1
1
1
代码如下：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int a[] = new int[15],x;
int n,i;
n = cin.nextInt();
for(i=1;i<=n;i++)
{
x = i;
while(x!=0)
{
a[x%10]++;
x /= 10;
}
}
for(i=0;i<=9;i++)
System.out.println(a[i]);
cin.close();
}
}
3.计算斐波那契数列第n项的值
问题描述:
斐波那契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……。在数学上，斐波纳契数列以递推的方法定义为：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥2，n∈N）。计算斐波那契数列第n项的值。
输入格式:
输入一个大于等于1，小于等于60的整数n。
输出格式:
输出第n项的数列值，数列值为double类型，不输出小数位数。
输入样例1:
20
输出样例1:
6765
代码如下：
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static int f(int x) {
if(x==1 ||x==2) {
return 1;
}else {
return f(x-1)+f(x-2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
double num;
num=f(n);
DecimalFormat formatDouble = new DecimalFormat("#"); //表示格式化为保留小数后六位
System.out.println(formatDouble.format(num));
}
}
4.按字典顺序输出n个数的全排列
问题描述：
请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。
输入格式:
给出一个正整数n（<10）。
输出格式:
输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列 
排在
之前，如果存在k使得a1 =b1,⋯,ak=bk 并且 
输入样例:
3
输出样例:
123
132
213
231
312
321
代码如下：
#include<stdio.h>
#include<string.h>
int a[10];
int book[10];
int n;
void dfs(int step)
{
int i,j,x,k;
k=step;
int next[11]={0,1,2,3,4,5,6,7,8,9,10};
if(step==n)
{
for(i=0;i<step;i++)
{
printf("%d",a[i]);
}
printf("\n");
return ;
}
for(i=1;i<=n;i++)
{
x=next[i];
if(!book[x])
{
a[step]=x;
book[x]=1;
dfs(k+1);
book[x]=0;
}
}
}
int main()
{
scanf("%d",&n);
memset(book,0,sizeof(book));
dfs(0);
return 0;
}
5.计算Ackerman函数
问题描述:
有两个整型变量m、n，Ackerman函数A(n，m)定义如下：
值，计算Ackerman函数A(n,m)的值。
输入格式:
在一行中输入2个正整数A和B，并用空格分隔。
输出格式:
输出Ackerman函数值。
输入样例:
3 2
输出样例:
8
代码如下：
import java.util.Scanner;
/*Ackerman函数的递归实现算法。
输入：输入两个数字，先输入n，后输入m。
输出：Ackerman函数计算后的值。
示例：输入：4 2，输出：16
Ackerman函数A(n，m)定义如下：
有两个独立的整型变量m、n：
当m=0,n=1时，A(1,0)=2;
当m>=0,n=0时，A(0,m)=1;
当m=0,n>=2时,A(n,0)=n+2;
当m>=1&& n>=1时，A(n,m)=A(A(n-1,m),m-1);
*/
public class Main {
public static int ackerman(int n, int m) {
int k=0;
if (m == 0 && n == 1) {
return 2;
}
if (m >= 0 && n == 0) {
return 1;
}
if (m == 0 && n >= 2) {
return n + 2;
}
if(m>=1&&n>=1){
k=ackerman(ackerman(n-1,m),m-1);
}
return k;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
System.out.println(ackerman(n,m));
}
}
6.汉诺（Hanoi）塔问题
古代某寺庙中有一个梵塔，塔内有3个座A、B和C，座A上放着64个大小不等的盘，其中大盘在下，小盘在上。有一个和尚想把这64 个盘从座A搬到座B，但一次只能搬一个盘，搬动的盘只允许放在其他两个座上，且大盘不能压在小盘上。现要求用程序模拟该过程，输入一个正整数n，代表盘子的个数，编写函数
void hanoi(int n,char a,char b,char c)
其中，n为盘子个数，从a座到b座，c座作为中间过渡，该函数的功能是输出搬盘子的路径。
输入格式:
输入在一行中给出1个正整数n。
输出格式:
输出搬动盘子路径。
输入样例:
3
输出样例:
a–>b
a–>c
b–>c
a–>b
c–>a
c–>b
a–>b
代码如下：
import java.util.Scanner;
public class Main {
public static void hanoi(int n,char a,char b,char c) {
if(n==1) {
System.out.printf("%c-->%c",a,c);
System.out.println();
}else {
hanoi(n-1,a,c,b);
System.out.printf("%c-->%c",a,c);
System.out.println();
hanoi(n-1,b,a,c);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char a='a';
char b='b';
char c='c';
hanoi(n,a,c,b);
}
}
7.众数问题
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。一般来说，多重集S中重数最大的元素为众数。例如，S={1,2,2,2,3,5}，S的众数是2，其重数为3。但是，如果有两个或两个以上的数出现次数都是最多的，那么这几个数都是这组数据的众数。例如：1，2，2，3，3，4的众数是2和3，并按众数在集合中出现的先后次序输出。如果所有数据出现的次数都一样，那么这组数据没有众数。例如：1，2，3，4，5没有众数。 对于给定的由n（n<2000)个自然数组成的多重集S，计算S的众数及其重数。
输入格式:
输入在一行中给出多重集S中的元素个数n；在接下来的n行中，每行有一个自然数。
输出格式:
有众数输出有2行，第1行是众数，第2行是重数。 无众数输出字符串"no mode."
输入样例1:
输入样例如下：
6
1
2
2
2
3
5
输出样例1:
输出样例如下：
2
3
代码如下：
#include<stdio.h>
int main() {
int S[2000]= {0};
int value[2000]= {0};
int num[2000]= {0};
int n,i,j;
int k=0;
int max_num;
scanf("%d",&n);
for(i =0; i<n; i++ ) {
scanf("%d",&S[i]);
}
value[0]=S[0];
for(i =0; i<n; i++) {
int flag=0;
for(j=0; j<=k; j++) {
if(S[i]==value[j]) {
num[j]++;
flag =1;
}
}
if(flag ==0) {
k++;
value[k]=S[i];
num[k]++;
flag = 0;
}
}
max_num =num[0];
for (i=1; i<=k; i++) {
if(num[i]>max_num)
max_num=num[i];
}
int xx=-1;
for(i=0; i<=k; i++) {
if(num[i]==max_num)
xx++;
}
if(xx==k) {
printf("no mode.");
return 0;
}
int s = 0;
for (i = 0; i<=k; i++) {
if(num[i]==max_num) {
if(s) putchar(' ');
s = 1;
printf("%d",value[i]);
}
}
printf("\n%d",max_num);
return 0;
}
8.A乘以B
从键盘输入任意两个整数A与B，位数15<n<100，采用Karatsuba’s algorithm计算其乘积.
输入格式:
输入给出2个位数在15和100之间的整数A和B，两数之间换行。
输出格式:
对每一组输入，输出A乘以B的值。
输入样例:
在这里给出一组输入。例如：
168746315641347979798909
164681654767446887797451316158
输出样例:
在这里给出相应的输出。例如：
27789422495727090869081808600903846422197378222471622
代码如下：
#include<stdio.h>
#include<string.h>
const int maxn = 1010;
char a[1010], b[1010];
int aa[1010], bb[1010], c[2020];
int main()
{
int i, j;
while (scanf("%s %s", a, b) != EOF)
{
if (a[0] == '0' || b[0] == '0')
{
printf("0\n");continue;
}
memset(c, 0, sizeof(c));
int l1 = strlen(a), l2 = strlen(b);
for (i = 0;i < l1;i++)
aa[i] = a[l1 - i - 1] - '0';
for (i = 0;i < l2;i++)
bb[i] = b[l2 - i - 1] - '0';
for (i = 0;i < l1;i++)
{
for (j = 0;j < l2;j++)
{
c[i + j] = aa[i] * bb[j] + c[i + j];
c[i + j + 1] = c[i + j + 1] + c[i + j] / 10;
c[i + j] = c[i + j] % 10;
}
}
i = l1 + l2;
while (!c[i]) i--;
for (;i >= 0;i--)
printf("%d", c[i]);
printf("\n");
}
return 0;
}