“藍橋杯”模擬法（一）——日期問題（2017年試題G）

1.模擬法簡介

模擬法，顧名思義，就是利用計算機模擬問題的求解過程，從而得到問題的解。模擬法由于簡單，因此又被稱為“不是算法的算法”。
模擬法是學習算法的基礎，通過模擬可以學習編程的各類技巧，提升初學者建立各種編程邏輯模型的感覺。大部分模擬題目直接模擬就可以求解,還有少量模擬題目需要考生簡化模擬過程，否則可能會使邏輯復雜，導致求解用時過長。
模擬法適用于問題求解清晰、運算規模較小的問題。如果問題求解的時空代價很大，就要考慮是否有其他更好的解決方案。

2.【案例解析】不高興的津津

津津上初中了。媽媽認為津津應該更加用功地學習,所以津津除了上學之外,還要參加媽媽為她報名的各科復習班。另外,媽媽每周還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過8小時就會不高興，而且上得越久就越不高興。假設津津不會因為其他事不高興,并且她的不高興不會持續到第二天。請你幫忙檢查津津下周的日程安排，看看她下周會不會不高興；如果會,那么她哪天最不高興。
輸入包括7行數據，分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數,用空格隔開,分別表示津津在學校上課的時間和媽媽安排她上課的時間。
輸出一個數字。如果津津不會不高興，則輸出0，如果會，則輸出最不高興的是周幾(用1,2,3,4,5,6,7分別表示周一，周二，周三，周四，周五，周六,周日)。如果有兩天或兩天以上不高興的程度一樣，則輸出時間最靠前的那一天。
例如，輸入下列數據：
5  3
6  2
5  3
5  4
0  4
0  6
則輸出為3。
本題可以采用模擬方法依次判斷哪天最不高興，并將最不高興的那.天輸出，在輸出過程中要注意以下幾個問題。
(1)判斷n個數中的最大值

max= 0;
for (i=1;i<=n;i++) //輸入n個數據
{
cin>>a;
if (a>max)
max=a; 
}

(2)數據存儲問題
本題的數據一共有7組，不算多，也不算少，可以直接運算，也可以將數據存儲到數組后再進行計算。
若不采用數組，則模擬的過程如下：

int a,b,s,max=0, i,day=0;
for (i=1;i<=7;i++)
{
cin>>a>>b;
s=a+b;
if ((s>max) && (s>8))
{max=s，day=i; }
}
cout<<day<<endl;

如果采用數組，則可以將數據存儲起來，在后續的操作中會更加方便，也更容易理解，采用數組模擬的方法如下：

int a,b, i, day, max, array[8];
char c;
for(i=1;i<=7;i++)
{
cin>>a>>b;
array[i]=a+b;
}
max=array[0];
for(i=1;i<=7;i++)
{
if (max<array[i])
{
max=array[i];
day=i;
}
if (max>8)
cout<<day<<endl;
else
cout<<0<<endl;

模擬法一般都不，但也會考查一些基礎算法，例如本題考查了如何在n個數中求最大值，及如何判斷津津的不高興條件。

3. 本次程序練習——日期問題(2017年試題G)（答案見下期）

【問題描述】
小明正在整理一批文獻,這些文獻中出現了很多日期，小明知道這些日期都在1960年1月1日至2059年12月31日之間。令小明頭疼的是,這些日期采用的格式非常不統一，有采用“年/月/日”的，有采用“月/日/年”的，還有采用“日/月/年”的。更加麻煩的是,年份都省略了前兩位，使得文獻上的一個日期存在很多可能的日期與其對應。
例如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。給出一個文獻上的日期，你能幫助小明判斷有哪些可能的日期與其對應嗎?
[輸入格式]
一個日期，格式是" AB/CD/EF" (0≤A,B,C,D,E,F≤9)。
[輸出格式]
輸出若干個不相同的日期，每個日期一行，格式是"yyyy- mm-dd"。多個日期按從早到晚的順序排列。
[樣例輸入]
02/03/04
[樣例輸出]
2002-03-04
2004-02-03
2004-03-02
提示：
本題的思路很簡單,將輸入的3個數據分別進行年、月、日的合法判斷，如果合法就輸出。但是求解本題要注意以下兩點。
(1)月份數據的表示
由于每月的天數沒有規律性，所以最好的方法就是利用數組將每月的天數表示出來，如:
int days[13]={0, 31, 28，31, 30，31, 30, 31, 31, 30，31, 30, 31};
這里還要注意閏年的問題，如果是閏年，則2月的數據就會不同，可以采用另個數組存儲，如:
int leapdays [13]={0，31, 29，31, 30, 31,30，31,31,30,31,30,31};
(2)合法年、月、日的存儲
對于一組數據， 可能會出現重復的合法年、月、日。例如，輸入01/01/01，則3組合法數據都是2001-01-01，所以這里要去重復。
(3)多個日期按從早到晚輸出。

4.上期參考答案

練習6 分解質因數
參考程序一——吳炳毅的答案

#include <iostream>
using namespace std;
int isPrime(int n)  //判斷是否為質數函數
{
 int num=0;
  for(int k=2;k<=n;k++)
  {
   if(n%k==0)return 1;
  }
  return 0;
}
int primefactors(int m)  //計算一個數的質因數
{
 int c=0;
 for(int j=2;j<=m;j++)
 {
   while(m%j==0&& isPrime(j))
  {
   c++;
   m=m/j;
  }
}
}
return c; 
}
int main() 
{
 int a,b;
 cout<<"input a and b:";
 cin>>a>>b;
 int sum=0;
 for(int i=a;i<=b;i++)
  sum+=primeFactors(i);
 cout<<sum<<endl;
}

參考程序二——申茂生答案

#include <iostream>
using namespace std;
int nextprime(int a)//輸出下一個質數 
{
 while(true)
 {
  int f=0;
  a++;
  for(int i=2;i<=a/2;i++)
  {
   if(a%i==0)
   {
    f=1;
    break;
   }
  }
  if(f==0)
   return a;
 }
}
int main()
{
 int a,b,sum1=0;
 cin>>a>>b;
 for(int i=a;i<=b;i++)//從a到b的范圍 
 {
  int sum2=0;
  for(int j=2;j<=i/2;j=nextprime(j))//j為質數，若j整除i，則j為質因數 
  {
   int c=i;
   while(c%j==0)//判斷j的冥次方是否整除i 
   {
    sum2++; 
    //去注釋可看質因數整除i過程cout<<c<<' '<<j<<' '<<sum1+sum2<<endl;
    c/=j;
   }
  }
  if(sum2==0)//若sum2為0則說明i為質數，可以整除本身 
   sum2=1;
  sum1+=sum2;
 }
 cout<<sum1;
}

練習7：回文數  參考程序

#include <iostream>
#include <cmath> 
//#include <string> 
using namespace std;
string rev(string s) // 字符串逆置
{
 string ss(s.rbegin(),s.rend());
 return ss; 
 } 
bool isPalindrome(string str)  //判斷字符串是否為回文 
{  
    //rbegin() 返回一個逆向迭代器，指向字符串的結尾（第一個字符的前一個位置）。
    // rend(); 返回一個逆向迭代器，指向字符串的開頭（第一個字符的前一個位置）。
 string rStr(str.rbegin(),str.rend());
 if(str==rStr)
  return true;
 else
  return false;
}
int swapDec(string str,int r)//r進制字符串向十進制數轉換
{
 int len=str.length();//字符串的長度
 int num=0; //十進制數
 for(int i=len-1;i>=0;i--)
 {
  //把數字字符轉換成數值數據
  int n;
  if(str[i]>='A'&&str[i]<='F') 
   n=str[i]-'A';
  else if(str[i]>='a'&&str[i]<='f')
       n=str[i]-'a';
  else n=str[i]-'0';
  num+=n*pow(r,i);
  } 
  return num;
 } 
 
 string  swapR(int n,int r) //十進制數轉換為r進制的字符串
 {
  string str="";//r進制字符串 
  while(n)
  {
   string t;
     int m=n%r;
     switch(m)
     {
      case 10: t="A"; break;
      case 11: t="B"; break;
      case 12: t="C"; break;
      case 13: t="D"; break;
      case 14: t="E"; break;
      case 15: t="F"; break;
      default:t=m+'0'; //整型轉換成字符串 
  }
    str=t+str; //拼接字符串 
    n=n/r; //修改n的值 
   } 
 return str; 
 } 
int main()
{
 int n; //進制 
 string m;//數據 
 cout<<"input n:";
 cin>>n;
 cout<<"input m:";
 cin>>m; 
 int counts=0;
 while(!isPalindrome(m)) //如果m不是回文
 {
  int x=  swapDec(m,n);//x是m的十進制數
  int y=  swapDec(rev(m),n);//y是m的逆序串的十進制數；
  int z=x+y;//z是兩個數的和
  m=swapR(z, n) ;// 修改m的值,接著去檢查m是否為回文 
  counts++;//計數器加1；
  if(counts>30) { //大于30次，則退出循環 
   break;  
   counts=-1;
  }
  } 
    cout<<counts<<endl;
 return 0;
}

微信公眾號搜索： 北京小學學習資料      家長升學指南    家長升學訓練營 關注公眾號，獲取最新資訊！  

掃碼添加“家長論壇”微信好友（微信號 16619908263）