首页 > 代码库 > 《计算机算法设计与分析》v4 第1章 算法概述 算法实现题答案

《计算机算法设计与分析》v4 第1章 算法概述 算法实现题答案

博主今年刚上大三,正好开算法这门课。由于博主本人比较喜欢算法但又比较懒,啃不动算法导论,所以决定拿这本书下手。

这本书是王晓东的第四版《计算机算法设计与分析》。初步打算将每章后面的算法题都用代码实现。

有些题跟某个ACM题目很像,我会把该ACM题的链接贴上。有的题没OJ交所以可能是错的。如有发现,还望指出。

1-1

统计数字问题

http://poj.org/problem?id=2282

这个题要按位分解,一位一位的来处理。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>using namespace std;int f[10];int digit[10];int p[10];int dp(int cur,int num,int val,bool fst,bool lst,int number){    if(cur==-1)  return 0;    if(!fst&&!lst&&f[cur]!=-1)        return f[cur];    int end=lst?digit[cur]:9;    int ans=0;    for(int i=0; i<=end; ++i)    {        if(i==val)        {            if(i==end&&lst)                ans+=(number%p[cur]+1)+dp(cur-1,i,val,i==0&&fst,i==end&&lst,number);            else if(i==0&&fst)                ans+=dp(cur-1,i,val,i==0&&fst,i==end&&lst,number);            else ans+=p[cur]+dp(cur-1,i,val,i==0&&fst,i==end&&lst,number);        }        else ans+=dp(cur-1,i,val,i==0&&fst,i==end&&lst,number);    }    if(!fst&&!lst)        f[cur]=ans;    return ans;}void solve(int *arr,int num){    int len=0;    int var=num;    while(num)    {        digit[len++]=num%10;        num/=10;    }    for(int i=0; i<=9; ++i)    {        memset(f,-1,sizeof(f));        arr[i]=dp(len-1,-1,i,1,1,var);    }}int main(){    p[0]=1;    for(int i=1; i<=9; ++i)        p[i]=p[i-1]*10;    int a;    while(scanf("%d",&a)!=EOF)    {        int x[10];        solve(x,a);        for(int i=0; i<10; ++i)            printf("%d\n",x[i]);    }    return 0;}
View Code

 1-2

字典序问题

这是本题的代码。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>#define LL long longusing namespace std;int f[10][30];int digit[10];int dp(int pos,int num,bool fst,bool lst){    if(pos==-1)    {        return !fst;    }    if(!fst&&!lst&&f[pos][num]!=-1)        return f[pos][num];    int beg=fst?0:num+1;    int end=(lst?digit[pos]:26);    int ans=0;    for(int i=beg; i<=end; ++i)    {        if(i>=num)        {            ans+=dp(pos-1,i,i==0&&fst,i==end&&lst);        }    }    if(!fst&&!lst)        f[pos][num]=ans;    return ans;}int main(){    char str[10];    while(scanf("%s",str)!=EOF)    {        memset(f,-1,sizeof(f));        int len=0;        for(int i=strlen(str)-1; i>=0; --i)            digit[len++]=str[i]-a+1;        printf("%d\n",dp(len-1,0,1,1));    }    return 0;}
View Code

由于这个题没找到原题,所以我写了一个暴力程序来检验对错。

#include<iostream>#include<cstdio>#include<vector>#include<string>using namespace std;int a[10];int n=6;bool judge(){    for(int i=1; i<n; ++i)        if(a[i-1]&&a[i]<=a[i-1])            return false;    return true;}int num;void dfs(int cur ){    if(cur>=n)    {        if(judge())        {            cout<<num++<<":"<<endl;            for(int i=0; i<n; ++i)                if(a[i]==0) putchar( );                else  putchar(a[i]+a-1);            putchar(\n);        }        return ;    }    for(int i=0; i<=26; ++i)    {        a[cur]=i;        dfs(cur+1);    }}int main(){    freopen("out.txt","w",stdout);    dfs(0);    return 0;}
View Code

 1-3

最多约数问题

这个题由于没有数据范围,所以变成了水题。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>#define LL long longusing namespace std;const int maxn=1000000;int numb[maxn];void init(){    for(int i=1; i<=maxn; ++i)        for(int j=i; j<=maxn; j+=i)            numb[j]++;}int main(){    int a,b;    init();    while(scanf("%d%d",&a,&b)!=EOF)    {        int best=0;        for(int i=a; i<=b; ++i)            if(numb[i]>numb[best])                best=i;        printf("%d\n",numb[best]);    }    return 0;}
View Code

1-4

金币阵列问题

首先要认识到从初始态最终达到了最终态,它们最后的第一列一定是相同的,这第一列可能是经过某一列交换或者原来的一列,再经过相应的行翻转得来的。所以我们只需要枚举第一列是从哪一列交换而来,再通过行翻转使第一列匹配,再交换其他列,判断能否得到最终态。在各种合法情况下取最优解。

代码未验证。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>#define LL long longusing namespace std;int n,m;int old[101][101];int now[101][101];int dest[101][101];void read(int a[][101]){    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            scanf("%d",&a[i][j]);}void copy(int src[][101],int dest[][101]){    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            dest[i][j]=src[i][j];}void flipRow(int row){    for(int i=1; i<=m; ++i)        now[row][i]^=1;}void swapCol(int a,int b){    for(int i=1; i<=n; ++i)        swap(now[i][a],now[i][b]);}bool isSame(int a,int b,int lhs[][101],int rhs[][101]){    for(int i=1; i<=n; ++i)        if(lhs[i][a]!=rhs[i][b])            return false;    return true;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        read(old);        read(dest);        int ans=-1;        for(int i=1; i<=m; ++i)        {            int ret=0;            copy(old,now);            if(!isSame(i,1,now,now))            {                swapCol(1,i);                ret++;            }            for(int j=1; j<=n; ++j)                if(now[j][1]!=dest[j][1])                {                    flipRow(j);                    ret++;                }            bool ok=false;            for(int j=2; j<=m; ++j)            {                ok=false;                for(int k=j; k<=m&&!ok; ++k)                {                    if(isSame(k,j,now,dest))                    {                        if(j!=k)                        {                            swapCol(j,k);                            ret++;                        }                        ok=true;                        break;                    }                }                if(!ok) break;            }            if(!ok) continue;            if(ans==-1) ans=ret;            else ans=min(ans,ret);        }        printf("%d\n",ans);    }    return 0;}
View Code

1-5

最大间隙问题

这个题有点意思,用鸽巢原理做。

代码未验证。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<vector>#define LL long longusing namespace std;int main(){    double a[100];    int n;    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; ++i)            scanf("%lf",&a[i]);        double low[100],high[100];        int count[101];        double mini=100000,maxi=0;        for(int i=1; i<=n; ++i)        {            mini=min(a[i],mini);            maxi=max(a[i],maxi);        }        for(int i=1; i<=n; ++i)        {            count[i]=0;            low[i]=maxi;            high[i]=mini;        }        for(int i=1; i<=n; ++i)        {            int buk=int(((n-1)*(a[i]-mini)/(maxi-mini)))+1;            count[buk]++;            if(a[i]<low[buk]) low[buk]=a[i];            if(a[i]>high[buk]) high[buk]=a[i];        }        double left=high[1],tmp=0;        for(int i=2; i<n; ++i)            if(count[i])            {                tmp=max(tmp,low[i]-left);                left=high[i];            }        printf("%f\n",tmp);    }    return 0;}
View Code

 

《计算机算法设计与分析》v4 第1章 算法概述 算法实现题答案