1004: [递归]母牛的故事

题目描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

输出
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入

2
4
5
0

样例输出

2
4
6

解题思路：

  • 第一年是一头母牛
  • 从第二年起母牛开始产生小母牛
  • 小母牛从第四年开始产生变成大母牛并产生小母牛
  • 先算出前七年的年数与母牛数比较（此时找规律）
  • 你会发现从第四年起，每一年的母牛数=前一年的+前三年的
年数 大母牛 第一年 第二年 第三年 总数
1 1 0 0 0 1
2 1 1 1 0 2
3 1 1 1 1 3
4 1 1 1 1 4
5 2 2 1 1 6
6 3 3 2 1 9
7 4 4 3 2 13 
#include <stdio.h>
int cmp(int n){
	if(n==1||n==2||n==3||n==4){
		return n;
	}else{
		return cmp(n-1)+cmp(n-3);
	}
}
int main () {
    int n;
	while(scanf("%d",&n)&&n){
		printf("%d\n",cmp(n));
	} 
    return 0;
}

1095：3n+1问题

题目描述
考虑以下生成数字序列的算法。从整数n开始。如果n是偶数，除以2。如果n是奇数，乘以3，再加上1。用n=1的新值重复这个过程，当n=1时终止。例如，对于n=22：22：11 34 17 52 26 13 40 10 5 16 8 4 2 1，将产生以下数列。我们猜测(但尚未证明)，对于每一个整数n，这个算法将以n=1结束。但是，对于所有整数，这个猜想至少可以维持到1，000，000。对于输入n，n的循环长度是在1之前生成并包含1的数。在上面的例子中，22的循环长度是16。给定任意两个数字i和j，就可以确定i和j之间所有数的最大循环长度，包括两个端点。
输入
输入将由一系列整数i和j组成，每一行一个整数对。所有整数将小于1，000，000和大于0。
输出
对于每一对输入整数i和j，输出i、j的顺序与它们在输入中出现的顺序相同，然后是i和j之间的整数的最大循环长度。这三个数字应该用一个空格分隔，所有三个数字都在一行上，每一行输入都有一行输出。
样例输入

1 10
100 200
201 210
900 1000

样例输出

1 10 20
100 200 125
201 210 89
900 1000 174

#include <stdio.h>
int main () {
    int i,j,k,max;
    while(scanf("%d %d",&i,&j)==2){
    	printf("%d %d ",i,j);
    	if(i>j){//如果i>j，交换位置 
    		max=i;i=j;j=max;//没有这个判断错误33% 
		}
		max=0; 
    	for(k=i;k<=j;k++){
    		int s=0;//次数初始化 
    		int t=k;
    		while(t!=1){
    			if(t%2==0){//偶数 
    				t=t/2;
    				s++;
				}else{//奇数 
					t=(t*3+1);
					s++;
				}	
			}
			s++;//循环次数 
			if(s>max){
				max=s;
			}	
		}
		printf("%d\n",max);
	}
    return 0;
}

1461: [蓝桥杯][基础练习VIP]FJ的字符串

题目描述
FJ在沙盘上写了这样一些字符串：

A1 = “A”

A2 = “ABA”

A3 = “ABACABA”

A4 = “ABACABADABACABA”

… …

你能找出其中的规律并写所有的数列AN吗？
输入
仅有一个数：N ≤ 26。
输出
请输出相应的字符串AN，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。
样例输入

3

样例输出

ABACABA

#include <stdio.h>
int cmp(int n){
	if (n==1){
		printf("A");
	}else{
		cmp(n-1);
		printf("%c",n+64);
		cmp(n-1);
	}
}//每一次输出的均是前一次的结果+N所代表代表的字母+前一次的结果
int main () {
    int n;
	scanf("%d",&n);
	cmp(n);
    return 0;
}

1462: [蓝桥杯][基础练习VIP]Huffuman树

题目描述
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：

  1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

  2. 重复步骤1，直到{pi}中只剩下一个数。

在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

  1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。

  2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。

  3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。

  4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。

  5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
    输入
    输入的第一行包含一个正整数n（n< =100）。

接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出
输出用这些数构造Huffman树的总费用。
样例输入

5 

5  3  8  2  9

样例输出

59

#include <stdio.h>
int cmp ( const void *a , const void *b ) 
{ 
  return *(int *)b - *(int *)a; 
}//从大到小排序 
int main () {
    int n,i,sum=0;
	scanf("%d",&n);
	int a[n],b[n];//读入数组a[n]，新数组b[n] 
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int length=n-1;
	for(i=0;i<n-1;i++){
		qsort(a,n-i,sizeof(a[0]),cmp);
		b[i]=a[length]+a[length-1];
		sum=b[i]+sum;
		a[length-1]=b[i];
		length--; 
	}
	printf("%d",sum); 
    return 0;
}

1463: [蓝桥杯][基础练习VIP]Sine之舞

题目描述
最近FJ为他的奶牛们开设了数学分析课，FJ知道若要学好这门课，必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏，寓教于乐，提高奶牛们的计算能力。
不妨设
An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
FJ想让奶牛们计算Sn的值，请你帮助FJ打印出Sn的完整表达式，以方便奶牛们做题。

输入
仅有一个数：N<201。
输出
请输出相应的表达式Sn，以一个换行符结束。输出中不得含有多余的空格或换行、回车符。
样例输入

3

样例输出

((sin(1)+3)sin(1-sin(2))+2)sin(1-sin(2+sin(3)))+1

解题思路:分析题目,发现有如下规律：

  • A1=sin(1)
  • A2=sin(1-sin(2))
  • A3=sin(1-sin(2+sin(3)))
  • S1=A1+1
  • S2=(A1+2)A2+1
  • S3=((A1+3)A2+2)A3+1

先在主函数构建S1,S2,S3的输出，然后再编写一个funA函数构建A1,A2,A3等等的输出即可

#include <stdio.h>
void cmp(int n){
	int i;
	for(i=1;i<=n;i++){
		printf("sin(%d",i);//先输出An的第一项sin(1
		if(i<n){
			if(i%2==0){
				printf("+",i);
			}else{
				printf("-",i);
			}
		}
	}
	for(i=0;i<n;i++){
		printf(")");
	}
}
int main () {
    int n,i;
	scanf("%d",&n);
	for(i=1;i<n;i++){
		printf("(");
	}
	for(i=1;i<=n;i++){
		cmp(i);
		printf("+%d",n-i+1);//输出后面的+n,或者+(n-1)等等 
		if(i<n){
			printf(")");//不是最后一项,都输出)
		}
	}
    return 0;
}

1464: [蓝桥杯][基础练习VIP]分解质因数

题目描述
求出区间[a,b]中所有整数的质因数分解。
提示

  • 先筛出所有素数，然后再分解。
  • 数据规模和约定
    2< =a< =b< =10000

输入
输入两个整数a，b。
输出
每行输出一个数的分解，形如k=a1a2a3…(a1< =a2< =a3…，k也是从小到大的)(具体可看样例)
样例输入

3  10

样例输出

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

1465: [蓝桥杯][基础练习VIP]回形取数

题目描述
回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入
输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。
输出
输出只有一行，共mn个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。
样例输入

3  3 

1  2  3 

4  5  6 

7  8  9

样例输出

1 4 7 8 9 6 3 2 5

#include <stdio.h>
int main(){
	int n,m,x,y,t;
	int a[201][201],b[201][201];//必须大于200
	scanf("%d %d",&n,&m);
	for(x=0;x<n;x++){
		for(y=0;y<m;y++){
			scanf("%d",&a[x][y]);
		}
	}
	t=1,x=0,y=0;//初始化值
	printf("%d",a[x][y]);
	b[x][y]=1;//初始首位
	while(n*m>t){
		while(x+1<n&& !b[x+1][y]){
			printf(" %d",a[++x][y]),b[x][y]=1,t++;//向下 
		}
		while(y+1<m&& !b[x][y+1]){
			printf(" %d",a[x][++y]),b[x][y]=1,t++;//向右 
		}
		while(x-1>=0&& !b[x-1][y]){
			printf(" %d",a[--x][y]),b[x][y]=1,t++;//向上 
		}
		while(y-1>=0&& !b[x][y-1]){
			printf(" %d",a[x][--y]),b[x][y]=1,t++;//向左 
		} 
	} 
	return 0;
}

1466: [蓝桥杯][基础练习VIP]字符串对比

题目描述
给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：

1：两个字符串长度不等。比如  Beijing  和  Hebei 

2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如  Beijing  和  Beijing 

3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如  beijing  和  BEIjing 

4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如  Beijing  和  Nanjing

编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入
包括两行，每行都是一个字符串
输出
仅有一个数字，表明这两个字符串的关系编号
样例输入

BEIjing 

beiJing

样例输出

3

思路

  • 当串长相等，先设置类别为2，假设两串相等，在随后搜寻串内字符过程中，若发现对应字符不等，再假设当大小写无关时，两串相等，设置类别为3，但是随后判断两串中对应字符的距离：若不等于32，两串显然不等，设置类别为4，并停止搜寻随后的字符。 
#include <stdio.h>
int main(){
	char a[10],b[10];
	scanf("%s %s",a,b);
	int n=strlen(a),m=strlen(b);
	int i,k;
	if(n!=m){//串长不等
		printf("1\n");
	}else{//假设两串相等
		for(k=2,i=0;i<n;i++){
			if(a[i]!=b[i]){
				k=3;//若对应字符不等
				if(32!=abs(a[i]-b[i])){//若对应两字符距离不等于32
					k=4;
					break;
				}
			}
		}
		printf("%d\n",k);
	} 
	return 0;
}

1467: [蓝桥杯][基础练习VIP]完美的代价

题目描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。

交换的定义是：交换两个相邻的字符

例如mamad

第一次交换 ad : mamda

第二次交换 ***dma

第三次交换 ma : madam (回文！完美！)

输入
第一行是一个整数N，表示接下来的字符串的长度(N < = 8000)

第二行是一个字符串，长度为N.只包含小写字母
输出
如果可能，输出最少的交换次数。

否则输出Impossible
样例输入

5 

mamad

样例输出

3

#include <stdio.h>
int main(){
	int n;
	scanf("%d\n",&n);//回车，坑点 
	char a[n];
	gets(a);
	int j=n-1,k=0,t=0;//字符串最后一个字符，交换次数，判读是否已经有一个单独的奇数的个数 
	int i,f,h,p;
	for(i=0;i<j;i++){//从第一个字符到倒数第二个字符遍历 
		for(f=j;f>=i;f--){//从最后一个开始，到第i个字符，寻找与a[i]相同的字符
			if(i==f){//如果没找到 ,说明存在奇数的情况。
				if(n%2==0 || t==1){//不可能的两种情况
					printf("Impossible\n");
					return 0;
				}
				t=1;//找到一个字符出现的次数为奇数 
				k=k+(n/2-i);//将次字符交换到中间位置的次数
			}else if(a[i]==a[f]){//如果找到了，将a[f]交换到a[end]位置 
				for(h=f;h<j;h++){//交换相邻两个位置的字符
					p=a[h];a[h]=a[h+1];a[h+1]=p;//交换字符串 
					k++;
				}
				j--;//末尾递减 
				break;//开始从i+1处重复操作
			}
		}
	}
	printf("%d",k);
	return 0;
}

1468: [蓝桥杯][基础练习VIP]报时助手

题目描述
给定当前的时间，请用英文的读法将它读出来。

时间用时h和分m表示，在英文的读法中，读一个时间的方法是：

如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“three o’clock”。

如果m不为0，则将时读出来，然后将分读出来，如5:30读作“five thirty”。

时和分的读法使用的是英文数字的读法，其中0~20读作：

0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。

30读作thirty，40读作forty，50读作fifty。

对于大于20小于60的数字，首先读整十的数，然后再加上个位数。如31首先读30再加1的读法，读作“thirty one”。

按上面的规则21:54读作“twenty one fifty four”，9:07读作“nine seven”，0:15读作“zero fifteen”。
输入
输入包含两个非负整数h和m，表示时间的时和分。非零的数字前没有前导0。h小于24，m小于60。
输出
输出时间时刻的英文。
样例输入

0 15

样例输出

zero fifteen

#include <stdio.h>
int main(){
	int h,m;
	scanf("%d %d",&h,&m);
	char *a[]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven",
	"twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty"};
	if(h>=0&&h<=20){
		printf("%s ",a[h]);
	}else if(h==21){
		printf("%s %s ",a[20],a[1]);
	}else if(h==22){
		printf("%s %s ",a[20],a[2]);
	}else if(h==23){
		printf("%s %s ",a[20],a[3]);
	}else if(h==24){
		printf("%s %s ",a[20],a[4]);
	}
	if(m==0){
		printf("o'clock");
	}else if(m>0 && m<=20){
		printf("%s",a[m]);
	}else if(m>20 && m<30){
		printf("%s %s",a[20],a[m-20]);
	}else if(m==30){
		printf("thirty");
	}else if(m>30 && m<40){
		printf("thirty %s",a[m-30]);
	}else if(m==40){
		printf("forty");
	}else if(m>40 && m<50){
		printf("forty %s",a[m-40]);
	}else if(m>50 && m<60){
		printf("fifty %s",a[m-50]);
	}
	return 0;
}