2013年蓝桥杯C++组真题解析1
题目1: 高斯日记
大数学家高斯有个好习惯：无论如何都要记日记。
他的日记有个与众不同的地方，他从不注明年月日，而是用一个整数代替，比如：4210
后来人们知道，那个整数就是日期，它表示那一天是高斯出生后的第几天。这或许也是个好习惯，它时时刻刻提醒着主人：日子又过去一天，还有多少时光可以用于浪费呢？
高斯出生于：1777年4月30日。
在高斯发现的一个重要定理的日记上标注着：5343，因此可算出那天是：1791年12月15日。
高斯获得博士学位的那天日记上标着：8113
请你算出高斯获得博士学位的年月日。
提交答案的格式是：yyyy-mm-dd, 例如：1980-03-21
解法一：Excel计算。 答案：1799-07-16
解法二：编程--简单的枚举
#include<iostream>
using namespace std;
bool isLeapYear(int y)
{
return (y%4==0 &&y%100!=0)||(y%400==0);
}
int main()
{
int y=1777;
int m=4;
int d=30;
for(int i=0;i<8112;i++)
{
d++;
if((m==1 || m==3 ||m==5 || m==7 || m==8 || m==10)&&(d==32))
{
d=1;
m++;
continue;
}
if((m==4 || m==6 || m==9 || m==11)&&(d==31))
{
d=1;
m++;
continue;
}
if(m==2 && isLeapYear(y) && d==30)
{
d=1;
m++;
continue;
}
if(m==2 && !isLeapYear(y) && d==29)
{
d=1;
m++;
continue;
}
if(m==12 && d==32)
{
d=1;
m=1;
y++;
continue;
}
}
cout<<y<<"-"<<m<<"-"<<d<<endl;
return 0;
}
题目2： 马虎的算式
小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
有一次，老师出的题目是：36 x 495 = ?
他却给抄成了：396 x 45 = ?
但结果却很戏剧性，他的答案竟然是对的！！
因为 36 * 495 = 396 * 45 = 17820
类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54
假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）
能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？
请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数
思路：因为是填空题-简单枚举
答案：142
#include <bits/stdc++.h>
using namespace std;
int main()
{
int ans=0;
for(int a=1;a<10;a++)
{
for(int b=1;b<10;b++){
if(a!=b)
for(int c=1;c<10;c++)
{
if(c!=a&&c!=b)
for(int d=1;d<10;d++)
{
if(d!=a&&d!=b&&d!=c)
for(int e=1;e<10;e++)
{
if(e!=a&&e!=b&&e!=c&&e!=d)
{
if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e)){
ans++;
}
}
}
}
}
}
}
cout<<ans<<endl;
return 0;
}
题目3: 第39级台阶
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
要求提交的是一个整数。
答案：51167078
//斐波那契的变形与进阶--这里使用递归求解，用动态规划更快，填空题首先保证算法正确
//模式匹配法：相似问题到现有问题
//先去掉偶数步的条件，每一步只能迈上1个或2个台阶一共有多少走法
//n为剩下的台阶数，f(n=39){return f(n-1)}+f(n-2)}
//step--用来跟踪已走的步数
#include <bits/stdc++.h>
using namespace std;
int ans=0;
void f(int n,int step)
{
if(n<0)
return ;
if(n==0 && step%2==0){
ans++;
return;
}
f(n-1,step+1);
f(n-2,step+1);
}
int main()
{
f(39,0);
cout<<ans<<endl;
return 0;
}
题目4：黄金连分数
黄金分割数0.61803... 是个无理数，
我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。
比较简单的一种是用连分数：
1
黄金数 = ---------------------
1
1 + -----------------
1
1 + -------------
1
1 + ---------
1 + ...
这个连分数计算的“层数”越多，它的值越接近黄金分割数。
请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。
小数点后3位的值为：0.618
小数点后4位的值为：0.6180
小数点后5位的值为：0.61803
小数点后7位的值为：0.6180340
（注意尾部的0，不能忽略）
你的任务是：写出精确到小数点后100位精度的黄金分割值。
注意：尾数的四舍五入！ 尾数是0也要保留！
显然答案是一个小数，其小数点后有100位数字，请通过浏览器直接提交该数字。
注意：不要提交解答过程，或其它辅助说明类的内容。
#include<bits/stdc++.h>
using namespace std;
/*
1.对给定的连分数进行分析，求出每一层的值。则发现可以转化为求斐波那契的第n和n+1项
2.n取多少？再增加n,小数点后101为不再发生改变
3.不能用C语言定义的整数型进行运算，而要手工地写大数的加法和除法(减法）
4.填空题 --可以使用java语言进行求解
*/
int n=400;//斐波那契的第n项
string add(string a,string b)//大数加法
{
//大数加法要熟练掌握，可瞬间敲出
a=a.substr(a.find_first_not_of('0'));//去掉前边多余的0
b=b.substr(b.find_first_not_of('0'));
long long lenA=a.length();
long long lenB=b.length();
long long len=max(lenA,lenB)+10;
reverse(a.begin(),a.end());//翻转，便于从低位开始求和
// reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值
reverse(b.begin(),b.end());
//begin()函数返回一个迭代器,指向字符串的第一个元素.;end()函数返回一个迭代器，指向字符串的末尾(最后一个字符的下一个位置)
string ans(len,'0');//初始化结果为：长度为：len;全部字符为：0
for(int i=0;i<lenA;i++)//把a拷贝到ans中
{
ans[i]=a[i];
}
int tmp=0;//tmp是上一位相加之后的进位
for(int i=0;i<len;i++)
{
if(i<b.length())
tmp+=(ans[i]-'0')+(b[i]-'0');//假设9+9为18
else
tmp+=(ans[i]-'0');
ans[i]=tmp%10+'0';//8
tmp/=10;//1
}
reverse(ans.begin(),ans.end());
return ans.substr(ans.find_first_not_of('0'));
}
int cmp(string a,string b)
{
if(a.find_first_not_of('0')==string::npos) a="0";
else a.find_first_not_of('0');
if(b.find_first_not_of('0')==string::npos) b="0";
else b.find_first_not_of('0');
if(a.length()>b.length()) return 1;
else if(a.length()<b.length()) return -1;
else{//长度相等
if(a<b) return -1;
else if(a>b) return 1;
else return 0;
}
}
string subtract(string a,string b)//这里的a一定大于等于b（a补0了）
{//完整的减法里面，a可能小于b,可交换a,b进行下面的代码
//1.翻转
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
//按位做减法
for(int i=0;i<b.length();i++)//a在做减法，在逐渐减少
{
if(a[i]>=b[i])
{
a[i]=a[i]-b[i]+'0';
}else{//需要借位。考虑不够借的情况
int k=1;
while(a[i+k]=='0')
{
a[i+k]='9';
k++;
}
//这里可以保证i+k位不是0
a[i+k]=a[i+k]-'1'+'0';
a[i]=(a[i]-'0'+10)-(b[i]-'0')+'0';
}
}
reverse(a.begin(),a.end());
if(a.find_first_not_of('0')==string::npos) return "0";//从头到尾都找不到非0值
return a.substr(a.find_first_not_of('0'));
}
string divide(string a,string b)//大数除法--转换成减法，这里只考虑a小于b的情况，
{
string ans="0.";
for(int i=0;i<101;i++){//101次
a.append("0");
int t=0;
while(cmp(a,b)>=0){//如果a>=b
a=subtract(a,b);//不停做减法
t++;//记录减法做了多少次，实际就是小数位
}
string t_str;
t_str=to_string(t);
ans.append(t_str);
}
return ans;
}
int main()
{
string a="1";//a,b初始化为斐波那契的前两项
string b="1";
for(int i=3;i<=n;i++)
{
string temp=b;
b=add(a,b);//自己要实现的大数加法
a=temp;
}
//a,b表示斐波那契的第n-1和第n项
string ans=divide(a,b);//自己要实现的大数除法
cout<<ans<<endl;
cout<<ans.length()-2<<endl;
return 0;
}
结果：
n=50:
0.61803398874989484820740990001204904326284254042472288566070913139408284656461170787663185198760678802
n=100:
0.61803398874989484820458683436563811772031274396379568575359185108829019869887522987627156252996318428
n=200
0.61803398874989484820458683436563811772030917980576286213544862270526046281890244971288825799042314041
n=300
0.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748
n=400
0.61803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748
最后结果：
0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375
如果使用java语言实现：
import java.math.BigDecimal;
public class huang {
public static void main(String[] args) {
int n=200;
BigDecimal a=new BigDecimal(1);
BigDecimal b=new BigDecimal(1);
for(int i=3;i<=n;i++)
{
BigDecimal temp=b;
b=b.add(a);
a=temp;
}
BigDecimal ans=a.divide(b,101,BigDecimal.ROUND_DOWN);
//ROUND_DOWN，是一个舍位取值的概念，我保留了两位小数，我不管你后面的小数值如何，也不会四舍五入，就硬生生的给阶段，
//相当于什么呢，就是我从小数点后面开始取两位，两位后面的都不要了，相当于一个截取字符串的操作。
System.out.print(ans);
}
}
题目5：前缀判断
如下的代码判断 needle_start指向的串是否为haystack_start指向的串的前缀，如不是，则返回NULL。 比如："abcd1234" 就包含了 "abc" 为前缀
#include <bits/stdc++.h>
using namespace std;
char* prefix(char* haystack_start, char* needle_start)
{
char* haystack = haystack_start;
char* needle = needle_start;//前缀
while(*haystack && *needle){//两个指针都没有越界的话
//if(______________________________) return NULL; //填空位置
//if的操作是移动指针并判断
if(*(haystack++)!=*(needle++))//++放后边，先取内容，再移动指针
return NULL;
}
if(*needle) return NULL;//如果needle没有越界的话。--指针肯定是要移动的。正常情况下needle更短，如果是前缀，则指针将移动到最后，指针越界
return haystack_start;
}
int main()
{
cout<<prefix("abcdefg","abc")<<endl;
cout<<prefix("abcdefg","abd")<<endl;
return 0;
}
题目6：三部排序
一般的排序有许多经典算法，如快速排序、希尔排序等。
但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。
比如，对一个整型数组中的数字进行分类排序：
使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!!
以下的程序实现了该目标。
其中x指向待排序的整型数组，len是数组的长度。
如果给定数组：
25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0
则排序后为：
-3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25
请分析代码逻辑，并推测划线处的代码，通过网页提交
注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！
#include <bits/stdc++.h>
using namespace std;
void sort3p(int* x, int len)//x指向待排序的整型数组，len是数组的长度。
{//快速排序的变体
int p = 0;
int left = 0;
int right = len-1;
while(p<=right){
if(x[p]<0){
int t = x[left];
x[left] = x[p];
x[p] = t;
left++;
p++;
}
else if(x[p]>0){
int t = x[right];
x[right] = x[p];
x[p] = t;
right--;
}
else{
//__________________________; //填空位置
p++;//仔细考虑动哪个指针
}
}
}
int main()
{
int arr[]={25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
sort3p(arr,14);
for(int i=0;i<14;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
后续真题持续更新。
