題目1: 高斯日記

大數(shù)學家高斯有個好習慣：無論如何都要記日記。
他的日記有個與眾不同的地方，他從不注明年月日，而是用一個整數(shù)代替，比如：4210
后來人們知道，那個整數(shù)就是日期，它表示那一天是高斯出生后的第幾天。這或許也是個好習慣，它時時刻刻提醒著主人：日子又過去一天，還有多少時光可以用于浪費呢？
高斯出生于：1777年4月30日。
在高斯發(fā)現(xiàn)的一個重要定理的日記上標注著：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： 馬虎的算式

小明是個急性子，上小學的時候經(jīng)常把老師寫在黑板上的題目抄錯了。
有一次，老師出的題目是：36 x 495 = ?
他卻給抄成了：396 x 45 = ?
但結果卻很戲劇性，他的答案竟然是對的??！
因為 36 * 495 = 396 * 45 = 17820
類似這樣的巧合情況可能還有很多，比如：27 * 594 = 297 * 54
假設 a b c d e 代表1~9不同的5個數(shù)字（注意是各不相同的數(shù)字，且不含0）
能滿足形如： ab * cde = adb * ce 這樣的算式一共有多少種呢？
請你利用計算機的優(yōu)勢尋找所有的可能，并回答不同算式的種類數(shù)。
滿足乘法交換律的算式計為不同的種類，所以答案肯定是個偶數(shù)
思路：因為是填空題-簡單枚舉
答案：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級臺階》，離開電影院的時候，他數(shù)了數(shù)禮堂前的臺階數(shù)，恰好是39級!
站在臺階前，他突然又想著一個問題：
如果我每一步只能邁上1個或2個臺階。先邁左腳，然后左右交替，最后一步是邁右腳，也就是說一共要走偶數(shù)步。那么，上完39級臺階，有多少種不同的上法呢？
請你利用計算機的優(yōu)勢，幫助小明尋找答案。
要求提交的是一個整數(shù)。
答案：51167078

//斐波那契的變形與進階--這里使用遞歸求解，用動態(tài)規(guī)劃更快，填空題首先保證算法正確
//模式匹配法：相似問題到現(xiàn)有問題
//先去掉偶數(shù)步的條件，每一步只能邁上1個或2個臺階一共有多少走法
//n為剩下的臺階數(shù)，f(n=39){return f(n-1)}+f(n-2)}
//step--用來跟蹤已走的步數(shù)
#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：黃金連分數(shù)

黃金分割數(shù)0.61803... 是個無理數(shù)，
我們?nèi)绾吻蟮命S金分割數(shù)的盡可能精確的值呢？有許多方法。
比較簡單的一種是用連分數(shù)：
? ????? 1
黃金數(shù) = ---------------------
? ??????? 1
? ? ? ?1 + -----------------
????????? ?1
??????? 1 + -------------
????????? ? ? 1
????????? 1 + ---------
????????? ? ? 1 + ...
這個連分數(shù)計算的“層數(shù)”越多，它的值越接近黃金分割數(shù)。
請你利用這一特性，求出黃金分割數(shù)的足夠精確值，要求四舍五入到小數(shù)點后100位。
小數(shù)點后3位的值為：0.618
小數(shù)點后4位的值為：0.6180
小數(shù)點后5位的值為：0.61803
小數(shù)點后7位的值為：0.6180340
（注意尾部的0，不能忽略）
你的任務是：寫出精確到小數(shù)點后100位精度的黃金分割值。
注意：尾數(shù)的四舍五入！ 尾數(shù)是0也要保留！
顯然答案是一個小數(shù)，其小數(shù)點后有100位數(shù)字，請通過瀏覽器直接提交該數(shù)字。
注意：不要提交解答過程，或其它輔助說明類的內(nèi)容。

#include<bits/stdc++.h>
using namespace std;
/*
1.對給定的連分數(shù)進行分析，求出每一層的值。則發(fā)現(xiàn)可以轉化為求斐波那契的第n和n+1項
2.n取多少？再增加n,小數(shù)點后101為不再發(fā)生改變
3.不能用C語言定義的整數(shù)型進行運算，而要手工地寫大數(shù)的加法和除法(減法）
4.填空題 --可以使用java語言進行求解
*/
int n=400;//斐波那契的第n項
string add(string a,string b)//大數(shù)加法
{
    //大數(shù)加法要熟練掌握，可瞬間敲出
    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函數(shù)用于反轉在[first,last)范圍內(nèi)的順序（包括first指向的元素，不包括last指向的元素），reverse函數(shù)沒有返回值
    reverse(b.begin(),b.end());
    //begin()函數(shù)返回一個迭代器,指向字符串的第一個元素.;end()函數(shù)返回一個迭代器，指向字符串的末尾(最后一個字符的下一個位置)
    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)//大數(shù)除法--轉換成減法，這里只考慮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++;//記錄減法做了多少次，實際就是小數(shù)位
        }
        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);//自己要實現(xiàn)的大數(shù)加法
        a=temp;
    }
    //a,b表示斐波那契的第n-1和第n項
    string ans=divide(a,b);//自己要實現(xiàn)的大數(shù)除法
    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語言實現(xiàn)：

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，是一個舍位取值的概念，我保留了兩位小數(shù)，我不管你后面的小數(shù)值如何，也不會四舍五入，就硬生生的給階段，
         //相當于什么呢，就是我從小數(shù)點后面開始取兩位，兩位后面的都不要了，相當于一個截取字符串的操作。
         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++))//++放后邊，先取內(nèi)容，再移動指針
            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：三部排序

一般的排序有許多經(jīng)典算法，如快速排序、希爾排序等。
但實際應用時，經(jīng)常會或多或少有一些特殊的要求。我們沒必要套用那些經(jīng)典算法，可以根據(jù)實際情況建立更好的解法。
比如，對一個整型數(shù)組中的數(shù)字進行分類排序：
使得負數(shù)都靠左端，正數(shù)都靠右端，0在中部。注意問題的特點是：負數(shù)區(qū)域和正數(shù)區(qū)域內(nèi)并不要求有序?？梢岳眠@個特點通過1次線性掃描就結束戰(zhàn)斗!!
以下的程序實現(xiàn)了該目標。
其中x指向待排序的整型數(shù)組，len是數(shù)組的長度。
如果給定數(shù)組：
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
請分析代碼邏輯，并推測劃線處的代碼，通過網(wǎng)頁提交
注意：僅把缺少的代碼作為答案，千萬不要填寫多余的代碼、符號或說明文字??！

#include <bits/stdc++.h>
using namespace std;

void sort3p(int* x, int len)//x指向待排序的整型數(shù)組，len是數(shù)組的長度。
{//快速排序的變體
    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;
}

后續(xù)真題持續(xù)更新。