台中女中b009~b010

b009: 無限猴子定理

讀入2個字串s1及s2，長度為n1、n2，問是否可由s2挑n1個字(順序不可對調)湊成s1

例如：{s1=ABC、s2=AXBXC}可，但{s1=YES、s2=YXyesS}不可：因找不到E
     又{s1=YES、s2=YXyesSE}也不可：因SE順序不對

宣告字串s1,s2、宣告整數n1,n2, i,j ：string s1,s2; int n1,n2,i,j;

讀入兩個字串 ： cin >> s1 >> s2;

設定字串長度： n1=s1.size(); n2=s2.size();

s2由i=0~n2-1一個一個往後找：  for(i=0,j=0;  i<n2 && j<n1;  ++i)

若與s1[j]同則j+1{j從0開始} ：     if( s2[i] == s1[j] ) ++j;

註：迴圈i>=n2或j>=n1結束{ for迴圈可同時設兩個初值以逗號隔開 }

迴圈結束時若j≠n1則表示s1沒找完整：if(j != n1) cout <<”NO” << endl;

            否則就是可以找到：      else cout <<”YES” << endl;

    

b010: 編碼破解

讀入1個字串s{只有大寫字母}解碼印出 {每個字母往前2格，C->A、D->B、…、B->Z、A->Y}

例如：{s= UVQR解碼後=STOP}，{s= FWVA解碼後=DUTY}

宣告字串s、宣告整數n, i,j ：string s; int n,i,j;

讀入字串 ： cin >> s;

設定字串長度： n=s.size();

迴圈i=0~n-1對S的每個字元：   for(i=0; i<n ; ++i) { 以下兩行   }

轉成0~25{A~Z}的對照碼 j：     j= (s[i]-'A'+24)%26;  //有更正

將對照碼轉成字元印出A~Z：    cout << char('A'+j);

印完所有字元後，再印換行  ：  cout << endl;

註：大寫字母A~Z的字元在電腦內部存成整數值A是65 ~ Z是90

例：UVQR

i	s[i]字	s[i]數	轉成j	char(‘A’+j)	印
0	U	85	18	char(83)	S
1	V	86	19	char(84)	T
2	Q	81	14	char(79)	O
3	R	82	15	char(80)	P

例：FWVA

i	s[i]字	s[i]數	轉成j	char(‘A’+j)	印
0	F	70	5	char(3)	D
1	W	87	20	char(20)	U
2	V	86	19	char(19)	T
3	A	65	0	char(24)	Y

台中女中b004~b008＼b005

b004: 一個都不能少

輸入2個正整數n,m，共有n個，回來m個，印出還沒回來的數 例如：

輸入的n=4,m=3 接著回來的3個數為 5 3 1 則印出 2 4

須宣告整數n,m、陣列a[20+1] ，因題目規定最多20個：int n,m, a[21];

讀入n,m：cin >>n >>m;

以下使用i,k 也要宣告： int i,k;

將a[i]全設為0 for(i=1; i<=n; ++i) a[i]=0;  // 6/12更新，因為從1開始算
讀入m個數k將 陣列a[k]設為1 ： for(i=0; i<m; ++i){ 以下兩行 }

     某一個回來的數字k ：              cin >> k;

     將對應的 a[k]設為1表示已回來了： a[k]=1;

沒被設為1的就是還沒回來： for(i=1; i<=n; ++i)

if (a[i]==0) cout << i <<” “;

印完所有數字後印換行： cout << endl;

b005稍難，另一篇再介紹 

b006: Hello, XXX!

輸入1個字串s，若為XXX，則輸出Hello, XXX! 

例如：輸入 Mary 則輸出 Hello, Mary!

須宣告字串變數s： string s;

讀入 s ： cin s;

印出Hello, 串上 s 及 ! ： cout <<” Hello, ” << s << “!” << endl;

b007: 倒背如流

輸入1個字串s, 將輸入的字串s依相反的字元順序輸出

例如：輸入Hello，則輸出 olleH

須宣告字串變數s： string s;

讀入 s ： cin >>s;

宣告整數 n = 字串長度-1 ： int n=s.size()-1;

以下使用i也要宣告： int i;

將字串字元由n~0印出： for(i=n; i>=0; --i) cout << s[i];

印完所有字元後印換行： cout << endl;

b008: 迴文

輸入1個字串s, 判斷是否迴文{左右對稱}例:ABBA或ABCBA

須宣告字串變數s： string s;

讀入 s ： cin >>s;

宣告 i 又 n為字串的長度： int i, n=s.size();

檢查前半及其對應的後半： for(i=0; i<n/2; ++i)

  若不相等就是非迴文：      if(s[i] != s[n-1-i]) break;

中間跳出的非迴文：   if(i<n/2) cout <<”NO” << endl;

                     else cout <<”YES” << endl;

台中女中b001~b003

b001: 最後倒數

輸入１個正整數n，依所輸入的n再輸入n個整數，倒著印出，例如：

輸入的n為4, 接著的4個數為 2 4 6 8 則印出 8 6 4 2

須宣告整數n、陣列a[10] ,i，因題目規定最多10個：int n, a[10],i;

讀入n：cin >>n;

讀入n個數至陣列a[i] ： for(i=0; i<n; ++i) cin >>a[i];

倒著印出，且數字間空1格： for(i=n-1; i>=0; --i) cout <<a[i]<<” “;

印完所有數字後印換行： cout << endl;

b002: 找最大值

輸入１個正整數n，依所輸入的n再輸入n個整數，找出最大值印位置及值，例如：

輸入的n為5, 5個數為 444 888 555 777 999 則印出 5 999

須宣告整數n、陣列a[10],i ，因題目規定最多10個：int n, a[10],i;

讀入n：cin >>n;

讀入n個數至陣列a[i] ： for(i=0; i<n; ++i) cin >>a[i];

設p=0, m=a[0]為最大： int p=0, m=a[0]

再由a[1]~a[n-1]找最大： for(i=1; i<n; ++i)

若比m大，則換成a[i]，並記住位置：if(a[i]>m) { m=a[i]; p=i; }

印出位置p+1及最大值m： cout <<p+1 <<” “ << m << endl;

b003: 資料分組

輸入１個正整數n，依所輸入的n再輸入n個整數，再輸入1個m，算出這n個數中
   比m大的個數有x個，比m小的個數有y個，印出 x y ，例如

輸入的n為5, 5個數為 5 4 3 2 1 , m為4 則印出 1 3

須宣告整數n,m、陣列a[10]：int n,m, a[10];

讀入n：cin >>n;

以下使用i也要宣告： int i;

讀入n個數至陣列a[i] ： for(i=0; i<n; ++i) cin >>a[i];

讀入m：cin >>m;

設x=0, y=0： int x=0 , y=0;

由a[0]~a[n-1]判斷>m或<m： for(i=0; i<n; ++i) {  以下兩行  }

若比m大，則x+1：if(a[i]>m) x++;

若比m小，則y+1：if(a[i]<m) y++;  // 6/11更正

印出x及y中間有空１格： cout <<x <<” “ << y << endl;

算出後序計的值

給一後序計算式，請算出其值

　例：有一後序式：1 2 + 5 3 - * 9 6 - /，算出其值為：2

{註由左至右遇運算符號時將其左兩數算出}

　　　1 2 + 5 3 - * 9 6 - /

中序轉後序

中序計算式 轉為 後序計算式

　例：將(1+2)*(5-3)/(9-6) 寫成沒有括號的後序式→ 1 2 + 5 3 - * 9 6 - /

求2~199之間的所有質數

畫10x10的格子，寫出所有奇數，
將第１格改為２標記為質數
３是質數，將３的倍數刪除，
５沒被刪掉也是質數，將５的倍數刪除，
７沒被刪掉也是質數，將７的倍數刪除，
１１沒被刪掉也是質數，將１１的倍數刪除，
１３沒被刪掉也是質數，將１３的倍數刪除，
１７沒被刪掉也是質數，將１７的倍數刪除，｛但<200的17的倍數已被刪過了}
所以只要13的倍數刪完，就已完成了！。

p1a,p1b,p1c,p1g 測驗日期及範圍

p1a,p1b  6/17 筆試小考 100%{含講義70%、程式邏輯及演算法30%}

p1a,p1b  6/24 C++實作期考 30% {含b001~b010及y044s,a020之類似題}

p1c 6/21 筆試期考100%{含講義70%、程式邏輯及演算法30%}

p1g 6/27 筆試期考100%{含講義70%、程式邏輯及演算法30%}

p1a,p1b  6/28~6/30 筆試期考 70%{含講義50%、程式邏輯及演算法20%}

程式邏輯及演算法 將另提供範例題講義例：

P1AB適用  配分 {筆試70%含Ch12-50%、本講義20%其中10%左右可由資安影片心得代替} C++30%{6/24}

第一題：請列出 a~b之間的所有質數 { 2 <= a , b <= 500 }

　例：141~199之間的質數有：149,151,157,163,167,173,179,181,191,193,197,199 共12個

第二題：中序計算式 轉為 後序計算式

　例：將(1+2)*(5-3)/(9-6) 寫成沒有括號的後序式→ 1 2 + 5 3 - * 9 6 - /

第三題：給一後序計算式，請算出其值

　例：有一後序式：1 2 + 5 3 - * 9 6 - /，算出其值為：2 {註由左至右遇運算符號時將其左兩數算出}

第四題：給一正整數 n ，請算出<n與n互質的 正整數有幾個？  例： n=12 <12與12 互質的有 1,5,7,11 共4個

第五題：給一正整數 n ，請算出其因數有幾個？

  例： 6的因數有 1,2,3,6共4個

第六題：給一正整數 n ，請算出其所因數的和？

  例： 6的因數和為  1+2+3+6 = 12

第七題：有一種數，叫做完美數，就是

其<n的所有因數和恰為n，給 n 問是否為完美數

  例： 6的 <6 因數和為  1+2+3 = 6

       28的<28因數和為  1+2+4+7+14 = 28

第八題：

Two integers, A and B, each between 2 and 100 inclusive, have been chosen. 2~100中選兩數a,b 不相同

The product, A×B, is given to mathematician Dr. P. The sum, A+B, is given to mathematician Dr. S.

H=a+b給S博士,G=a*b給P博士 They each know the range of numbers. Their conversation is as follows:

P: "I don't have the foggiest idea what your sum is, S."    (1)P博「我看不出你的H是多少」

S: "That's no news to me, P. I already knew that you didn't know. I don't know either."

(2)S博「我知你不知」  P: "Aha, NOW I know what your sum must be, S!"   (3)P博「我已知H是多少」

S: "And likewise P, I have figured out your product!!"  (4)S博「我也知G是多少」

What are the numbers?.  請問a,b？ {假設a<b}  可參考維基「和與積的問題」

P1CG適用   {期末 筆試100% p1c(6/21)、p1g(6/27) 配分 ch12講義70%

本講義30%其中10~15%左右可由資安影片心得代替}

第一～第五題　及第九～第十一題

第九題：　4x4或8x8的幻方

　例4x4格將1~16填入後直的、橫的、斜的 ４格的和皆相同

 8x8的先分成4個4x4如下

第十題：1A2B遊戲邏輯推理：找其中任一組解

　例 {猜1357:1A1B, 猜2468:1B, 猜0369:2B, 猜1230:2A1B}，問猜多少會 4A

第十一題：數字推理類：找其中任一組解

例：下列式子的 a b c d e f g h i j 各代表數字 0~9且不重複，g≠0， a<c<f ， b<e ，問 a~j各代表的數字為何？