“蓝桥杯”模拟法（二）——REPEAT 程序、解码（真题）
-
-
梁老师 北京小升初老师～
0 人点赞了该文章 · 108 浏览
1. REPEAT 程序(2020年试题D)
【问题描述】
附件prog.txt中是一个用某种语言编写的程序。
其中,REPEAT k表示一个次数为k的循环。循环控制的范围通过缩进表达，从次行开始连续的缩进比该行多的(前面空白更长的)为循环包含的内容。
例如:
A=0
REPEAT 2:
A=A+4
REPEAT 5:
REPEAT 6:
A=A+5
A=A+7
A=A+8
A=A+9
该片段中,从“A= A + 4”所在的行到“A= A + 8”所在的行都在第一行中循环2次。
从“REPEAT 6:”所在的行到“A= A + 7”所在的行都在“REPEAT 5:"中循环。“A= A + 5”实际的循环次数是2×5×6 = 60次。 “A= A + 7”实际的循环次数是2×5 = 30次。“A= A + 9”不在循环中，执行1次。
请问该程序执行完毕后A的值是多少?
提示：
该程序是典型的程序模拟题目,但这个模拟比较复杂，下面首先看一下如何笔算本题，计算过程如下:
2×[4+5×(6×5+7)+8]+9
=2×4+2×5×6×5+2×5×7+2×8+9
=8+300+70+ 16+9
= 403
这里的关键是看式子2×4+2×5×6×5+2×5×7+2×8+9.
该式子一共有5项， 每项均由以下两部分组成。
(1)循环次数
循环次数分别是2、2×5×6、2×5、2 、1。该循环次数的计算可以根据循环的层次决定，即循环控制范围的缩进。缩进越多，层次越多，循环次数就越多，缩进越少，层次越少，循环次数就越少。
通过观察可知，循环次数首先逐渐增多，然后逐渐减少，减少的顺序是逆序方式，这种方式就是栈的特性，所以可以利用栈的形式模拟过程，如下图所示，栈中是每层的循环次数。
图1 每层的循环次数
下图是每一层前的空格数，通过空格数判断是否进入下一层。循环次数的控制，即该入栈还是出栈是由代码每行的缩进量(缩进空白字符数)决定的，因此本题也另外建立了一个栈，用来存储每行的空白字符数，和循环次数栈一起计算出入栈的顺序。具体的出入栈如图2所示。
图2 每层的空格数
说明：prog.txt个文件有1023行，没有写到文件中，需要的可以去网上下载，或使用前面9行进行测试或私信我。
参考程序如下：
# include <iostream>
using namespace std;
const int N=100;
string str;
int level[N]; //用来存放当前层的空白字符数
int stack[N]; //栈用来存放当前层的循环次数
int top=0; //栈顶元素的下标
int main()
{
int space= 0; //每行前面的空格數
int cnum= 1; //总循环数
int ans=0; //结果
level[0]=-1,//空格数初始化为-1
stack[0]=1; //循环次数栈底初始化为1
freopen("prog.txt", "r",stdin); //从文件中读每一行
//从文件中获取输人
getline(cin,str) ; //首行数据"A= 0"处理 扔掉
while (getline(cin,str))
{ //从读第二行开始
int len= str.size(); //本行的字符个数
space=0; //每次重新对空格计数
while(str[space]==' ') //计算本行前面的空格数
space++ ;
while (space<= level [top]) //小于等于上一层的空格数
cnum/=stack[top-- ]; //出栈，循环次数减少
if(str[len-1]==':') { //是REPEAT语句
int k=str[len-2]-'0'; //当前循环重复的次数
cnum*=k; // 循环次数增加
top++; //来到新的一层
level [top]= space; //把空格数存入空格栈
stack[top]=k; //把本层的循环次数存入循环次数栈
}
else //不是循环语句
{
int k=str[len-1]-'0'; //要加上的数
ans+=cnum* k;
}
}
cout<<ans<<endl;
return 0;
}
2. 解码(2020年试题G)（答案见下期）
【问题描述】
小明有一串很长的英文字母，可能包含大写和小写。在这串字母中，有很多字母是连续且重复的。小明想了一个个将这串字母表达得更短的办法：将连续的几个相同的字母写成“字母+出现次数”的形式。例如，连续的5个a，即aaaaa可以简写成a5(也可以简写成a4a aa3a等)。对于这串字母: HHllloo,小明可以简写成H3el5o2。为了方便表达小
明不会将超过9个连续相同的字母写成简写的形式。现在给出简写后的字符串,请帮助小明将其还原成原来的字符串。
[输入格式]
输入一个字符串。
[输出格式]
输出一个字符串，表示还原后的字符串。[样例输入]
H3el5o2 [样例输出]
HHH ellllloo
[评测用例规模与约定]
对于所有评测用例，字符串均由大小写英文字母和数字组成,长度不超过100。注意:原来的字符串长度可能超过100。
提示：
本题可以采用模拟法求解，将每个元素都遍历一遍即可，分为以下两种情况。
①若当前元素是字符，且下一个元素是数字，则需要循环输出当前字符，循环输出的次数就是数字的值。
②若当前元素和下一个元素都是字符，则将这个字符输出一遍。
3.上期答案——日期问题
参考程序一
#include <iostream>
#include <algorithm>
using namespace std;
bool isLeap(int y) //是否为闰年
{
if(y%400==0||y%100!=0&&y%4==0) //闰年
return true;
return false;
}
//平年每个月的天数
int monthDays[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//闰年每个月的天数
int leapMonthDays[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
//判断是否为有效的日期
bool isValidDate(int year,int month,int day)
{if(year>=60) year=1900+year;
else year=2000+year;
if(month>12) return false;
if(isLeap(year)) //闰年
for(int i=1;i<=12;i++)
{
if(day>leapMonthDays[i]) //日是否有效
return false;
}
else //平年
for(int i=1;i<=12;i++)
{
if(day>monthDays[i]) //日是否有效
return false;
}
return true;//返回是有效日期
}
int main()
{
int dates[3];//有效日期数组
string dateT;//输入日期 字符串 如"02/03/04"
cout<<"input date:";
cin>>dateT;
string str1= dateT.substr(0,2); //02
string str2= dateT.substr(3,2); //03
string str3= dateT.substr(6,2); //04
int d1=atoi(str1.c_str()); //2
int d2=atoi(str2.c_str()); //3
int d3=atoi(str3.c_str()); //4
int i=0; //有效日期个数
int j;
if(isValidDate(d1,d2,d3)) //年月日
{
int year=d1;
if(year>=60) year=1900+year;
else year=2000+year;
int n= year*10000+d2*100+d3; // 20020304
dates[i]=n;
i++;
}
if(isValidDate(d3,d1,d2)) //月日年
{
int year=d3;
if(year>=60) year=1900+year;
else year=2000+year;
int n=year*10000+d1*100+d2;// 20040203
for(j=0;j<i;j++)
{if (dates[j]==n)
break;
}
if(j==i) //数组里没有这个日期
{dates[i]=n; // 存入数组
i++;
}
}
if(isValidDate(d3,d2,d1)) //日月年 04 03 02
{
int year=d3;
if(year>=60) year=1900+year;
else year=2000+year;
int n=year*10000+d2*100+d1;// 20040302
for( j=0;j<i;j++)
{if (dates[j]==n)
break;
}
if(j==i) //数组里没有这个日期
{dates[i]=n; // 存入数组
i++;
}
}
//对数组元素进行从小到大进行排序
sort(dates,dates+i);
for(int j=0;j<i;j++)
{
cout<<dates[j]/10000<<"-"<<dates[j]%10000/100<<"-"
<<dates[j]%100<<endl;
}
return 0;
}
参考程序二——申茂生答案
#include <iostream>
using namespace std;
void outymd(int y,int m,int d)//输出
{
if(y>59)
y+=1900;
else
y+=2000;
cout<<y<<'-';
if(m<10)
cout<<'0';
cout<<m<<'-';
if(d<10)
cout<<'0';
cout<<d<<endl;
}
int leapyear(int y)//判断闰年
{
if(y%400==0||y%100!=0&&y%4==0)
return 0;
else
return 1;
}
int main()
{
int date[3]={};
char c;
int ymd[3][3]={};
int md[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
cin>>date[0]>>c>>date[1]>>c>>date[2];
//判断是否符合年月日样式
if((date[1]==2&&date[2]<=(md[2]-leapyear(date[0])))||date[1]!=2&&date[1]<=12&&date[2]<=md[date[1]])
{
ymd[0][0]=date[0];
ymd[0][1]=date[1];
ymd[0][2]=date[2];
}
//判断是否符合月日年样式
if((date[0]==2&&date[1]<=(md[2]-leapyear(date[2])))||date[0]!=2&&date[0]<=12&&date[1]<=md[date[0]])
{
ymd[1][0]=date[2];
ymd[1][1]=date[0];
ymd[1][2]=date[1];
}
//判断是否符日月年样式
if((date[1]==2&&date[0]<=(md[2]-leapyear(date[2])))||date[1]!=2&&date[1]<=12&&date[0]<=md[date[1]])
{
ymd[2][0]=date[2];
ymd[2][1]=date[1];
ymd[2][2]=date[0];
}
for(int i=2;i>0;i--)//将时间早的排到前面
{
for(int j=0;j<i;j++)
{
if((ymd[j+1][0]<ymd[j][0])||(ymd[j+1][0]==ymd[j][0]&&ymd[j+1][1]<ymd[j][1])||(ymd[j+1][0]==ymd[j][0]&&ymd[j+1][1]==ymd[j][1]&&ymd[j+1][2]<ymd[j][2]))
{
int t1=ymd[j+1][0],t2=ymd[j+1][1],t3=ymd[j+1][2];
ymd[j+1][0]=ymd[j][0];
ymd[j+1][1]=ymd[j][1];
ymd[j+1][2]=ymd[j][2];
ymd[j][0]=t1;
ymd[j][1]=t2;
ymd[j][2]=t3;
}
else if(ymd[j+1][0]==ymd[j][0]&&ymd[j+1][1]==ymd[j][1]&&ymd[j+1][2]==ymd[j][2])//时间相等将前面的赋值为0
{
ymd[j][0]=0;
ymd[j][1]=0;
ymd[j][2]=0;
}
}
}
for(int i=0;i<3;i++)
{
if(ymd[i][0]!=0&&ymd[i][1]!=0)
outymd(ymd[i][0],ymd[i][1],ymd[i][2]);
}
}
添加 家长论坛微信
全部 0条评论