2006年CS上机解答参考

发信人: davidsoft(david), 信区: KaoyanExam
标  题: 2006年CS上机解答参考
发信站: 饮水思源 (2006年03月29日23:53:42 星期三)

也许有不对的地方，发上来供大家讨论
//A.cpp offered by http://spaces.msn.com/davidblogs/
//18 lines
#include "iostream"
#include "fstream"
using namespace std;

int fib(int n)
{
        if (n==0) return 0;
        else if (n==1) return 1;
        else return fib(n-1)+fib(n-2);
}

void main()
{
        fstream f("fib.in");
        int n;
        f>>n;
        cout<<fib(n)<<endl;
}


//B.cpp offered by http://spaces.msn.com/davidblogs/
//28 lines
#include "iostream"
#include "fstream"
#include "string"
#include "stdio.h"
using namespace std;

char table[100]="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";

void main()
{
        fstream f("wertyu.in");
        char c[1000];
        string s;
        int tablelen = strlen(table);
        while (!f.getline(c,1000).eof())
        {
                s = c;
                int n = s.length();
                for (int i=0;i<n;i++)
                {
                        for (int j=0;j<tablelen;j++)
                        {
                                if (s==table[j]) s=table[j-1];
                        }
                }
                cout<<s<<endl;
        }
}


//C.cpp offered by http://spaces.msn.com/davidblogs/
//24 lines
#include "iostream"
#include "fstream"
#include "string"
using namespace std;

int match(string s,string t)
{
        int count=0;
        string::size_type index = -1;
        while ((index = s.find(t,index+1))!=string::npos) count++;
        return count;
}

void main()
{
        fstream f("matching.in");
        string s,t;
        while (!f.eof())
        {
                f>>s;
                f>>t;
                cout<<match(s,t)<<endl;
        }
}


//D.cpp offered by http://spaces.msn.com/davidblogs/
//60 lines
#include "iostream"
#include "fstream"
#include "string"
using namespace std;

int getminex(int n)
{
        int k=0;
        int l=1;
        while (1)
        {
                if (n<l) break;
                else
                {
                        l=l*2;
                        k++;
                }
        }
        return k-1;
}

int getremain(int n)
{
        int t=getminex(n);
        int s=1;
        for (int i=0;i<t;i++)
        {
                s=s*2;
        }
        return n-s;
}

string getform(int n)
{
        if (n==0) return "";
        else if (n==1) return "2(0)";
        else if (n==2) return "2";
        else if (n==4) return "2(2)";
        else
        {
                string t,s;

                int e = getminex(n);
                if (e == 1) t = "";
                else t = "("+getform(e)+")";               
                s = "2"+t;

                int r = getremain(n);
                if (r != 0) s = s+"+"+getform(r);
                return s;
        }
}

void main()
{
        fstream f("form.in");
        int n;
        f>>n;
        cout<<getform(n)<<endl;
}
--

法律硕士　　　

第三道题的效率达不到要求，应该考虑用kmp算法

请问CS上机是不是用C也可以啊