2013年ブルーブリッジカップ省試合本題解析(上)(C/C++大学B組)

文書ディレクトリ

2013年ブルーブリッジカップ省試合本題解析(上)

(C/C++大学B組)

ガウス日記:

いい加減な計算式:

第39段階段:

注意:

黄金連点数:

という問題には,高精度加算,減算,除算が含まれている.

学習stringクラスの材料として好適である

接頭辞判断:

2013年ブルーブリッジカップ省試合本題解析(上)
(C/C++大学B組)
ガウス日記:

#include
using namespace std;
bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0)||(year % 400 == 0);
}
#define _for(i, x, y) for(int i = x;i < y;i++)
int main(){
    int year = 1777;
    int month = 4;
    int day = 30;
    const int mon_arr[] = {-1,31,28,31,30,31,30,31,31,30,31,30,31};
    const int days = 8113 - 1;
    _for(i,0,days){
        //              
        day++;
        if(month == 2 && day >= 29){
            if(isLeapYear(year))
                if(day == 30) {
                    month = 3;
                    day = 1;
                }
            if(!isLeapYear(year))
                if(day == 29)
                {
                    month = 3;
                    day = 1;
                }
            continue;
        }
        if(day == mon_arr[month] + 1){
            day = 1;
            if(month == 12) {
                year += 1;
                month = 1;
            } else
                month++;
        }
    }
    cout<<year<<" "<<month<<" "<<day<<endl;
    return 0;
}

いい加減な計算:

#include
#include
using namespace std;
#define _for(i,start,end) for(int i = start;i <= end;i++)
int main(){
    //abcde
    //ab * cde = adb * ce
    int temp1,temp2,count = 0;
    set<int> Set;
    _for(a,1,9)
        _for(b,1,9)
            _for(c,1,9)
                _for(d,1,9)
                    _for(e,1,9){
        		//set     ，    ，  a = b,   c,d,e     
        //       ，        ，        ，     。
                        Set.insert(a);
                        Set.insert(b);
                        Set.insert(c);
                        Set.insert(d);
                        Set.insert(e);
                        if(Set.size() < 5){
                            Set.clear();
                            continue;
                        }
                        temp1 = (a*10+b)*(c*100+d*10+e);
                        temp2 = (a*100+d*10+b)*(c*10+e);
                        if(temp1 == temp2)
                            count++;
                        Set.clear();
                    }
    cout<<count;
    return 0;
}

#include
using namespace std;
#define _for(i,start,end) for(int i = start;i <= end;i++)
int main() {
    //abcde
    //ab * cde = adb * ce
    int temp1, temp2, count = 0;
    _for(a, 1, 9)_for(b, 1, 9) {
            if (b != a)
                _for(c, 1, 9) {
                    if (c != a && c != b)
                        _for(d, 1, 9) {
                            if (d != a && d != b && d != c)
                                _for(e, 1, 9) {
                                    if (e != a && e != b && e != c && e != d) {
                                        temp1 = (a * 10 + b) * (c * 100 + d * 10 + e);
                                        temp2 = (a * 100 + d * 10 + b) * (c * 10 + e);
                                        if (temp1 == temp2)
                                            count++;
                                    }
                                }
                        }
                }
        }
    cout<<count;
    return 0;
}

39段目:

#include
using namespace std;
int walk(int left,int count){
	int sum = 0;
    if(left - 1 >= 0)
        sum += walk(left - 1,count + 1);
    if(left - 2 >= 0)
    	sum += walk(left - 2,count + 1);
    if(left == 0)//        
		if(count % 2 == 0)
			return 1;
		else
			return 0;
	return sum;
}
int main() {
    int count = 0;
    cout<<walk(39,count);
    return 0;
}

注意:
この問題は空欄の問題で、暴力は再び答えを出せばいい.(穴埋め問題の自転車は何ですか)リュックサックを考えると、kという階段に2つの値が格納されていることをよく考えなければなりません.1つは奇数歩を歩く値で、1つは偶数歩を歩く値です.例えば、階段が0の場合(left=0の場合)、奇数歩は0、偶数歩は1に戻ります.
黄金の連続点:

からフィボラッチを求めるnとn+1項

に移行する.

nはいくら取りますか?さらにnを増加すると、小数点後101ビットは

変化しない.

cはc言語で定義された整数型の直接演算ではなく、大数加算と除算(減算)

を手書きで書く.
注:javaの大きな整数ライブラリで答えを算出できます(試合は裏でjavaを使うことができるかどうかはわかりません)
この問題には高精度加算、減算、除法が含まれている.
完璧ではないが、大まかな考え方を指摘した.
stringクラスの学習に適した材料

#include
#include 
#include 
using namespace std;
string add(string a,string b){
    /**
            ，
        a,b        。string ans(len,'0')，  a   ans。
         a[i] + b[i]   ans[i] + b[i],    a           。
         ，  b         ,  ans   '0'   。
         len = max(lenA,lenB)
       a    ，     b    ，    ans[i]
     */
     //     0,"000123" -> "123"
     a = a.substr(a.find_first_not_of('0'));
     b = b.substr(a.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(b.begin(),b.end());
     string ans(len,'0');//      len ，     0
     // a   ans 
     for(int i = 0;i < lenA; i++){
         ans[i] = a[i];
     }
     int tmp = 0;
     for(int i = 0; i < len; i++){
         if(i < b.length())
            tmp += (ans[i] - '0') + (b[i] - '0');
         else
             tmp += (ans[i] - '0');
         ans[i] = tmp % 10 + '0';
         tmp /= 10;//tmp          
     }
     reverse(ans.begin(),ans.end());

    return ans.substr(ans.find_first_not_of('0'));
}
int cmp(string a,string b){
    //  a   0
    //unsigned long i1 = a.find_first_not_of('0');
    if(a.find_first_not_of('0') == string::npos)a="0";
    else a.substr(a.find_first_not_of('0'));
    if(b.find_first_not_of('0') == string::npos)b="0";
    else b.substr(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;
        if(a > b)return 1;
        //a == b
        else return 0;
    }
}
string subtract(string a,string b){
    //    a    b
    //     ，a    b,     ，  a,b       
    //1.  
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    //2.     
    //for(int i = 0;i < b.length(); i++)   i++   ++i  
    for(int i = 0;i < b.length(); i++){
        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
            //my
            a[i+k] = a[i+k] - '1'+'0';
            a[i] = (a[i] - '0' + 10) -(b[i] - '0') + '0';
        }
    }
    reverse(a.begin(),a.end());
    //  a.find_first_not_of('0'),    a==b  ，ans = "0";      0,     
    //    ，       a == b;
    if(a.find_first_not_of('0') == string::npos)return "0";
    return a.substr(a.find_first_not_of('0'));
}
void i2s(int t,string &str){
    int len_t = 0;
    string temp = "0";
    if(t == 0)
        str.append(temp);
    while(t){
        temp = t%10 + '0';
        str.append(temp);
        t /= 10;
        len_t++;
    }
    reverse(str.begin(),str.end());
}
string divide(string a,string b){
    //   a <= b   
    string ans = "0.";//             
    //     
    for(int i = 0; i < 101; i++){
        a.append("0");
        int t = 0;
        while(cmp(a,b)>=0){
            a = subtract(a,b);//     
            t++;//         
        }
        string t_str;
        //   i2s   
        i2s(t,t_str);
        ans.append(t_str);
    }
    return ans;
}
int main() {
    string a = "1";
    string b = "1";
    for(int i = 3;i <= 500;i++){
        string tmp = b;
        b = add(a,b);
        a = tmp;
    }
    string ans = divide(a,b);
    cout<<ans<<endl;
    cout<<ans.length() - 2<<endl;
    //      ，    4 5 
    return 0;
}

接頭辞の判断:
次のコードでneedleを判断します.startが指す列がhaystack_かどうかstartは、列の接頭辞を指し、そうでない場合はNULLを返します.
例えば、「abcd 1234」には「abc」が含まれています.接頭辞

#include
#include 
#include 
using namespace std;
/**
 *
 * @param haystack_start   
 * @param needle_start   
 * @return
 */
char* prefix(char* haystack_start,char* needle_start){
    //needle_start   haystack_start   
    char* haystack = haystack_start;
    char* needle = needle_start;
    while(*haystack && *needle) {
        // 2       ，              ，    
        if (*(haystack++) != *(needle++)) {
            return NULL;
        }
    }
    //           ，       ，   
    //if(*needle)      needle       ，     haystack needle  ，
    //  needle_start  haystack   ，  NULL
    if(*needle)
        return NULL;
    //if(*needle)  ，  needle haystack 。 while      ，
    // needle    haystack_start       ，  needle haystack   。
    return haystack_start;
}

int main() {
    char a[] = "abcd1234";
    char b[] = "abc";
    cout<<prefix(a,b);
    // prefix("abcd1234","abc");
    return 0;
}