程序设计思维与实践第十一十二周实验小结
11周作业
A题
房子价格是 200万，以每年百分之 K增长，每年积攒 N万，问第几年能够买下这套房子。
第一年积攒N万，房价200万；第二年积攒2N万，房价200（1+K）万，第三年积攒3N万，房价200（1+K)^2 万 ……每一年都比较积攒数与房子价格，当积攒数大于等于房子价格时，为可以购买。当超过限定时间时视为不可购买。
#include<iostream>
using namespace std;
int main(){
int N;
double K;
double price=200.0;
int year=1,flag=0;
cin>>N>>K;
K=K/100.00;
while(flag==0&&year<=20){
if(price<=year*N){flag=1;}
else {price=price+price*K;year++;}
}
if(flag==1){cout<<year<<endl;}
else {cout<<"Impossible"<<endl;}
return 0;}
B题
n^2个同学排列成一个 n∗n的方阵，用 0 表示男生，用 1表示女生。给定两种方阵方案，判断前一种方阵能否旋转为后一种方阵。
不需要翻转：前一方阵的任意位置的值都与后一方阵对应位置的值相等。
顺时针旋转九十度：前一方阵第i行第j个元素与后一方阵第n-1-i列第j个元素对应相等。
顺时针旋转一百八十度：前一方阵第i行第j个元素与后一方阵第n-1-i行第n-j-1个元素对应相等。
顺时针旋转二百七十度：前一方阵第i行第j个元素与后一方阵第i列第n-j-1个元素对应相等。
不符合上述情况则不能旋转。
#include<iostream>
using namespace std;
int a[20][20];
int b[20][20];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>b[i][j];}}
int x=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=b[i][j]){
x=-1;
break;
}}}
if(x==-1){
x=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=b[j][n-1-i]){
x=-1;
break;
}}}
}
if(x==-1){
x=2;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=b[n-1-i][n-1-j]){
x=-1;
break;
}}}
}
if(x==-1){
x=3;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=b[n-1-j][i]){
x=-1;
break;
}}}
}
cout<<x<<endl;
return 0;}
C题
给定明文密文对应规则，对密文解密得到明文。
由题目所给对应规则可知，对于大部分明文字母，其密文是其之后第五个字母。之所以是大部分，是因为V-Z不存在之后五位的字母。我们按照次序给其进行A-E的密文分配。由此我们得知明文密文对应规则为密文=第（明文+5）%26位字母，当密文大于明文时，明文=第（密文-5）%26位字母，反之，明文=第（密文+26-5）%26位字母。由对应规则得到明文。
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
using namespace std;
int main(){
string s;
getline(cin,s);
for(int i=0;i<s.length();i++){
if(s[i]>='A'&&s[i]<='E'){
s[i]=s[i]+26-5;
}
else if(s[i]>='F'&&s[i]<='Z'){
s[i]=s[i]-5;
}
}
cout<<s<<endl;
}
D题
找到一段最长的序列，该序列中1的数量等于2的数量，且前一半全是一种，后一半全是另外一种。
对于任意一段全为1的序列，它可以与其之前一段全为2的序列组合，也可以与其之后一段全为2的序列组合；对于全为2的序列也是同样的道理。由一段全为1的序列和一段全为2的序列组成的合法序列的最大长度取决于两段序列中长度较小者。例如，111122最长合法序列长度为4，为序列2的两倍。因此，我们每找到一种组合，就由该组合下较短序列的长度确定组合中合法序列的最大长度。遍历所有组合，我们便找到了最长的合法序列。
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int sum1=0,sum2=0,num=0,max=0,pre=0;
for(int i=0;i<n;i++){
cin>>num;
if(num==1){
if(pre!=2){sum1++;}
else {
if(sum1==0){sum1++;}
else{
if(sum1>=sum2){if(max<2*sum2) max=2*sum2;}
else if(sum1<sum2){if(max<2*sum1) max=2*sum1;}
sum1=1;
}}}
if(num==2){
if(pre!=1){sum2++;}
else {
if(sum2==0){sum2++;}
else{
if(sum1>=sum2){if(max<2*sum2) max=2*sum2;}
else if(sum1<sum2){if(max<2*sum1) max=2*sum1;}
sum2=1;
}}}
pre=num;
}
if(sum1>=sum2){if(max<2*sum2) max=2*sum2;}
else if(sum1<sum2){if(max<2*sum1) max=2*sum1;}
cout<<max<<endl;
}
E题
给定所请求的现金量 纸币面额和该纸币的数量。输出不超过现金量的最大可支付数。
由于给定纸币面额的同时，限定了该纸币的数量。所以这道题是一道典型的多重背包问题，将不同纸币的数量进行二进制拆分转换为0,1背包问题来解决。为节约空间，0,1背包采用逆序。
#include<iostream>
#include<cstring>
using namespace std;
int cash,N,n[11],d[11],c[10001],s[100010];
int main(){
while(cin>>cash){
cin>>N;
for (int i=0;i<N;i++)
cin>>n[i]>>d[i];
int cnt=0;
for (int i=0;i<N;i++){
int t=n[i];
for (int k=1;k<=t;k<<=1){
c[cnt]=k*d[i];
t-=k;
cnt++;
}
if(t>0){
c[cnt]=t*d[i];
cnt++;
}
}
for(int i=0;i<cnt;i++)//普通01
for(int j=cash;j>=c[i];j--)
s[j]=max(s[j],s[j-c[i]]+c[i]);
cout<<s[cash]<<endl;
memset(s,0,sizeof(s));
}
return 0;
}
F题
给定开车时间，唱片数量和每一张唱片的播放长度。输出总时长不超过开车时间的听歌方案与时长。
由于开车时间相对较长，而唱片数量相对较少，我将这道题视为超大背包来解决。而由于唱片数量足够小，所以无需进行拆分，所以简单用枚举子集的办法就可以得到最长时长和此时的方案。
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
void dfs(int num,int *a,int *b,int *c,int N,int M,int sum,int flag,int &max){
if(flag==0&&sum<=N){
if(num<M){
b[num]=0;
dfs(num+1,a,b,c,N,M,sum,flag,max);
b[num]=1;
sum=sum+a[num];
dfs(num+1,a,b,c,N,M,sum,flag,max);}
else {
if(max<sum&&sum<=N){
max=sum;
for(int i=0;i<M;i++){c[i]=b[i];}
flag=1;}
}}}
int main(){
int N;
while(scanf("%d",&N)!=EOF){
int M;
cin>>M;
int a[M];
int b[M];
int c[M];
for(int i=0;i<M;i++){
cin>>a[i];
b[i]=0;
}
int sum=0,flag=0,max=0;
dfs(0,a,b,c,N,M,sum,flag,max);
for(int i=0;i<M;i++){
if(c[i]==1){
cout<<a[i]<<" ";
}
}
cout<<"sum:"<<max<<endl;
}}
11周模拟题
T1
给定一个序列，输出序列的段数。（段定义：连续的相同的最长整数序列）
从第二个元素开始遍历，如果与前一位置元素相同，证明在同一段中，段数不变。反之，则在不同段中，段数加一，遍历完毕即得到最终段数。
#include<iostream>
using namespace std;
int a[1010];
int main()
{
int n;
cin>>n;
int num=1;
for(int i=0;i<n;i++){cin>>a[i];}
for(int i=1;i<n;i++)
{
if(a[i]!=a[i-1]){
num++;
}}
cout<<num<<endl;
}
T2
给定一个棋盘，一个格子一种颜色。当一行或一列上有连续三个或者更多相同颜色的棋子时，颜色消除（一个棋子可以在某一行和某一列同时被消除），输出消除后的棋盘。
消除：对于棋盘任何一行或一列，我们记录在该行或该列中连续的颜色相同的棋子数量。若数量不小于3，则对这些棋子进行颜色消除。为避免行的消除对列的影响或列的消除对行的影响，我们将行与列的消除分开进行，只要消除过一次，则颜色就被消除。
#include<iostream>
using namespace std;
int a[35][35];
int b[35][35];
int main()
{
int n,m;
cin>>n>>m;
int sum=1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
b[j][i]=a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=1;j<m;j++){
if(a[i][j]==a[i][j-1]){
sum++;
if(j==m-1){
if(sum>2){
for(int k=0;k<sum;k++){a[i][j-k]=0;}}
sum=1;}
}
else{
if(sum>2){
for(int k=1;k<=sum;k++){
a[i][j-k]=0;}}
sum=1;}
}
}
for(int i=0;i<m;i++){
for(int j=1;j<n;j++){
if(b[i][j]==b[i][j-1]){
sum++;
if(j==n-1){
if(sum>2){
for(int k=0;k<sum;k++){b[i][j-k]=0;}}
sum=1;}
}
else{
if(sum>2){
for(int k=1;k<=sum;k++){
b[i][j-k]=0;}}
sum=1;}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]==0||b[j][i]==0){cout<<"0";}
else{cout<<a[i][j];}
if(j<m-1){cout<<" ";}}
if(i<n-1) cout<<endl;
}
}
T4
给定一个字符串，计算字符串中delicious子串的数量。delicious子串定义：当且仅当每一个字符都属于一个大于1的回文串。
根据题意，delicious串分为两种：回文串和由回文串连接构成的字符串。如果按照这个思路固然可以算出所有delicious串，但在字符串长度极大时情况无疑会十分复杂。我们不妨反过来思考：什么样的子串不是delicious串？经过分析：子串的第一个元素为一种，剩余元素为一种与子串最后一个元素为一种，剩余元素为一种的情况才不构成deliciou串。由此，我们可以找出1所有非delecious串，由总串数减去非delecious串数，我们就得到了所有delicious串数。
#include<iostream>
#include<string>
using namespace std;
int main()
{ int n;
cin>>n;
string s;
cin>>s;
long long int ans;
ans=1ll*(n-1)*n/2;
int p=0;
int num=0;
for(int i=1;i<n;i++){
if(s[i-1]!=s[i]){
ans=ans-(i-p);
p=i;}}
p=0;
for(int i=1;i<n;i++)
if(s[i-1]!=s[i])
{ p=i-1;
while(s[i]==s[i+1]){
i++;
}
ans=ans-(i-p);
num++;
}
ans=ans+num;
cout<<ans;
return 0;
}
12周
A题
给出n个数，找出出现至少(n+1)/2次的数。
对于输入的序列我们先进行排序（保证相同的数位置相邻）。从第一个位置开始遍历，找出每一个数的数量，数量不小于(n+1)/2直接输出，反之继续查找。
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000001];
int main(){
int N;
while(cin>>N){
for(int i=0;i<N;i++){
cin>>a[i];
}
sort(a,a+N);
a[N]=-1;
int sum=1;
for(int i=0;i<N;i++){
if(a[i]==a[i+1]){sum++;}
else{
if(sum>=(N+1)/2){ cout<<a[i]<<endl;break;}
sum=1;}
}}
return 0;
}
B题
三维迷宫寻找路径，每次只能向上下左右前后移动，判断路径是否存在及走出迷宫消耗时间。
三维迷宫最短路径问题，与二维迷宫相似，从起点开始进行广度优先搜索。到达终点时的路径长度即为最小时间。
#include<iostream>
#include<queue>
using namespace std;
struct point
{
int z,x,y;
};
int space[30][30][30];
point pre[30][30][30];
int dxyz[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int main(){
int L,R,C;
char c;
point s,e,q;
while(cin>>L>>R>>C&&L!=0&&R!=0&&C!=0){
for(int i=0;i<L;i++){
for(int j=0;j<R;j++){
for(int k=0;k<C;k++){
cin>>c;
if(c=='#'){space[i][j][k]=1;}
else if(c=='.'){space[i][j][k]=0;}
else if(c=='S'){space[i][j][k]=0;s.z=i;s.x=j;s.y=k;}
else if(c=='E'){space[i][j][k]=0;e.z=i;e.x=j;e.y=k;}}}}
queue<point> Q;
Q.push(s);
space[s.z][s.x][s.y]=1;
bool flag=false;
while(!Q.empty()&&!flag)
{
for(int i=0;i<6;i++)
{
q.x=Q.front().x+dxyz[i][1];
q.y=Q.front().y+dxyz[i][2];
q.z=Q.front().z+dxyz[i][0];
if(q.x>=0&&q.x<R&&q.y>=0&&q.y<C&&q.z>=0&&q.z<L&&space[q.z][q.x][q.y]!=1)
{
Q.push(q);
space[q.z][q.x][q.y]=1;
pre[q.z][q.x][q.y]=Q.front();
if(q.z==e.z&&q.x==e.x&&q.y==e.y)
{
flag=true;
break;
}}}
Q.pop();
}
if(flag){
int sum=0;
while(q.z!=s.z||q.x!=s.x||q.y!=s.y)
{
int z=q.z,x=q.x,y=q.y;
q.z=pre[z][x][y].z;
q.x=pre[z][x][y].x;
q.y=pre[z][x][y].y;
sum++;
}
cout<<"Escaped in "<<sum<<" minute(s)."<<endl;}
else {cout<<"Trapped!"<<endl;}}
return 0;}
C题
每个寝室里面有ai个人。从第i到第j个宿舍一共有sum(i,j)个人，找到sum(i1, j1) + … + sum(im,jm)的最大值。且m段都不能相交。
无论到哪一个宿舍，都会出现两种可能：一是与其他宿舍一起组成其中的一段，另一种是另起新的一段。我们取其中的最大值作为到达该宿舍的最大值。重复m次，对每个最大值进行遍历，我们就得到了m次加法中的最大值。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int a[1000010];
int dp[1000010];
int s[1000010];
int main()
{
int m,n;
while(cin>>m>>n)
{ memset(dp,0,sizeof(dp));
memset(s,0,sizeof(s));
int sum=0;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
for(int i=1;i<=m;i++)
{
sum=-9999999;
for(int j=i;j<=n;j++)
{
dp[j]=max(dp[j-1]+a[j],s[j-1]+a[j]);
s[j-1]=sum;
sum=max(sum,dp[j]);
}
}
cout<<sum<<endl;
}
return 0;
}
下一篇： 苹果和Google，电信界的新星