算法入门经典第三章课后习题

萌新一个，初次开始写博客。由于最近在学习刘佳汝的算法，所以想把自己所学所得记录下来，方便自己以后再回顾，有不足之处多多指出，万分感谢！（第一、二章内容相对简单，直接从第三章开始）
1.（得分）给出一个由O和X组成的串（长度为1~80），统计得分。每个O的得分为目前连续出现的O个数，X的得分为0，例如OOXXOXXOOO得分为1+2+0+0+1+0+0+1+2+3，
输入有多行
题目比较简单，思路也很明确，用一个sum存储截止到当前字符的O的个数，total计算总得分

#include<iostream> 
#include<cstring> 
using namespace std;  
int main(){  
int N;  
cin>>N;  
while(N--){  
char s[80];  
cin>>s;  
int flag=0,sum=0,total=0;     
for(int i=0;i<strlen(s);i++){  
if(s[i]=='O')flag=1;        //flag用来标记当前字符是否为0 
else {sum=flag=0;}  
if(flag==1)sum++;  
        total+=sum;  
    }  
cout<<total<<endl;  
}  
}

2.（分子量）给出一种物质的分子式，求分子量。本题中分子式只包含4种原子，分别为C,H,O,N，原子量分别为12.01,1.008，16.00,14.01g/mol。例如C6H5OH分子量为94.108，输入有多行

#include<iostream> 
#include<cstring> 
#include<cctype> 
#include<iomanip> 
using namespace std;  
const float C=12.01,H=1.008,O=16.00,N=14.01;  
int main(){  
char a[80];  
memset(a,'a',sizeof(a));  
int T;  
cin>>T;  
while(T--){  
float sum=0;  
cin>>a;  
for(int i=0;i<strlen(a);i++){  
float m;  
int num;  
switch(a[i]){  
case 'C':m=C;break;  
case 'H':m=H;break;  
case 'O':m=O;break;  
case 'N':m=N;break;  
        }  
if(isdigit(a[i+1])&&isdigit(a[i+2])){//后两位都是数字 
        num=(a[i+1]-'0')*10+(a[i+2]-'0');  
        i+=2;                               //跳过这两个数字 
        }  
else if(isdigit(a[i+1])&&!(isdigit(a[i+2]))){   //后一位是数字 
        num=a[i+1]-'0';  
        i+=1;  
        }                                  //跳过该数字 
else if(!isdigit(a[i+1])||strlen(a)==1){num=1;} //后面是字母或者是字符串尾 
        sum+=m*1.0*num;  
    }  
cout<<fixed<<setprecision(3)<<sum<<endl;  
    }  
return 0;  
}

我用的方法很笨，分情况讨论，这样做其实并不好，有数组越界的风险，也去网上看过了其他人的做法，的确比这个好得多。但是由于是自己手写的，还是记录下来。
3.（数数字）输入一个整数n，把从1-n顺序写在一起：123456789101112……n，数一数0-9各出现多少次，输入有多行，输出10个整数，用空格分隔
思路：把1-n循环一遍，求出相应的各个数位上的数字即可

#include<iostream> 
#include<cstring> 
using namespace std;  
int main(){  
int T,N,a[10];  
cin>>T;  
while(T--){  
memset(a,0,sizeof(a));   
cin>>N;  
int x,temp;  
for(int i=1;i<=N;i++){  
                x=i;  
while(x>0){  
                temp=x%10;    //求出个位上的数字 
                ++a[temp];    //对应的数字数组值自增1 
                x/=10;        //求出去掉个位后的x 
            }  
        }  
for(int i=0;i<10;i++){  
if(!i)cout<<a[i];  
else cout<<" "<<a[i];  
if(i==9)cout<<endl;  
        }  
    }  
return 0;  
}

4.（周期串）如果一个字符串可以由某个长度为k的字符串复制多次得到，则称该串以k为周期，例如，abcabcabc以3为周期（注意他也以3和6为周期）
输入一个长度不超过80的字符串，输出其最小周期。输入有多行

#include<iostream> 
#include<cstring> 
using namespace std;  
int main()  
{  
char a[85];  
int l,flag,i,j;  
int N;  
cin>>N;  
while(N--){  
cin>>a;  
    l = strlen(a);  
for(i=1;i<=l;i++)      
    {  
        flag=1;  
for(j=i;j<l;j++)     
if(a[j]!=a[j%i]) //将第j个跟第一个周期对应的字符比较 
            {  
                flag=0;    
break;      
            }  
if(flag)      
        {  
cout<<i<<endl;  
break;  
        }  
    }  
}  
return 0;  
}

先假设i是最小周期，然后将后面的字符串和原串中的对应的第一个到第i个字符依次比较，如果都相同，则i是周期

秒客网

算法入门经典第三章课后习题

相关文章