2015年2月12日 星期四

國中部 C++ 甄選講義

講義的word檔 (好像IE無法開啟?),以下為複製過來、版面可能有點變形
你適合學C++嗎?
1、         現在不會C++沒關係、我們從頭開始教{有耐心即可}
2、         但是必須要對邏輯推理、或益智遊戲有興趣
3、        篩選30名左右的測驗可能會出以下的題目
(1)
請列出200~500之間的質數{學C++後問100萬以內所有的質數}
(2)
給一個數獨盤請解出、或給數組數字及幾A幾B請解出
 例:已猜1357(2A0B)、2468(1A1B)、1368(2A0B)、7258(3A0B)、問多少會4A
(3)5
位數a被1位或2位數k整除得5或4位數b,但a,b所有數字不重覆
 例: (a)79546 ÷ (k)62 =  (b)01283 其中 7,9,5,4,6,0,1,2,8,3皆不重覆
(4)
請列出5階幻方第2列第5格(2,5)的數字? { 若(1,3)格是1、(5,2)格是2 }
(5)
河內塔搬5環A->C最少步(共31步)的第22步?
(6)簡單的加法?   以下式子中的英文字母各代表 0~9其中一個,相同的字母代表相同的數字
 代入正確的數字後,算式才會正確 

F
O
R
T
Y


請寫出每個字母所代表的數字



T
E
N


F
O
R
T
Y
E
N
S
I
X
+


T
E
N













S
I
X
T
Y


所填的數字 0~9不重複

1: 1 A->C
2: 2 A->B
3: 1 C->B
4: 3 A->C
5: 1 B->A
6: 2 B->C
7: 1 A->C
8: 4 A->B
9: 1 C->B
10: 2 C->A
11: 1 B->A
12: 3 C->B
13: 1 A->C
14: 2 A->B
15: 1 C->B
16: 5 A->C
17: 1 B->A
18: 2 B->C
19: 1 A->C
20: 3 B->A
21: 1 C->B
22: 2 C->A
23: 1 B->A
24: 4 B->C
25: 1 A->C
26: 2 A->B
27: 1 C->B
28: 3 A->C
29: 1 B->A
30: 2 B->C
31: 1 A->C
前100質數表
2,3,5,7,11,13,17,19,23,29
31,37,41,43,47,53,59,61,67,71
73,79,83,89,97,101,103,107,109,113
127,131,137,139,149,151,157,163,167,173
179,181,191,193,197,199,211,223,227,229
233,239,241,251,257,263,269,271,277,281
283,293,307,311,313,317,331,337,347,349
353,359,367,373,379,383,389,397,401,409
419,421,431,433,439,443,449,457,461,463
467,479,487,491,499,503,509,521,523,541
  8階和是260



                       


2~9:   奇階3,5,7,9同一方法  、    4,8階另一方法     、  6階第3種方法以後再說



參考解答的word檔
以下簡介參考解,另有補充的可至 http://rs-vb.blogspot.tw 部落格參考
篩選30名左右的測驗可能會出以下的題目 參考解及說明     (測驗日期開學後另通知)
(1)
請列出200~500之間的質數 共有49個質數、最大的是499
(2)給一個數獨盤請解出、或給數組數字及幾A幾B請解出  1258是4A
 例:已猜1357(2A0B)、2468(1A1B)、1368(2A0B)、7258(3A0B)、問多少會4A
(3)5
位數a被1位或2位數k整除得5或4位數b,但a,b所有數字不重覆       本題會簡化,較複雜需電腦
 例: (a)79546 ÷ (k)62 =  (b)01283 其中 7,9,5,4,6,0,1,2,8,3皆不重覆
(4)
請列出5階幻方第2列第5格(2,5)的數字? { 若(1,3)格是1、(5,2)格是2 }
(5)
河內塔搬5環A->C最少步(共31步)的第22步? 第22步是將 2號環從C搬至A寫成 2CA
(6)簡單的加法?   以下式子中的英文字母各代表 0~9其中一個,相同的字母代表相同的數字
 代入正確的數字後,算式才會正確 

F
O
R
T
Y


請寫出每個字母所代表的數字



T
E
N


F
O
R
T
Y
E
N
S
I
X
+


T
E
N


2
9
7
8
6
5
0
3
1
4

S
I
X
T
Y


所填的數字 0~9不重複
(4)7階、8階幻方如下:




質數的求法可看維基的「埃拉托斯特尼篩法」

其它有關測驗的試題,過兩天會補充一些資料

2015年2月8日 星期日

P2A練習02/05

P2A 2015/02/05練習:讀入n個數,問數字相同的個數最多幾個?

以下為第(2)種方法的程式碼,另附測試檔 a.txt b.txt c.txt 
a共110個數字{有5個5} 、  b共10000個數字{有6個100}、 c共10000個數字{有8個98765432}

/*
p2a 02/05 練習:若有 N 個數 A[0],A[1],.....A[N-1],求重複最多的個數
例 有10個數 1,2,3,4,5,2,3,4,5,2,最多為3個 {註:2有3個}
本題(1) 若A[0]~A[N-1]的範圍不大<10^6的話{假設為M},可用空間換取時間,直接宣告C[M]來計數即可,
  (2) 但若範圍太大{0~10^9 },而N不太大<10^4的話,可將A陣列排序後,以下列程式碼來計算最多個數
(3) 也可以使用類似 b05的解法
*/
#include <iostream>
#include <algorithm>  // 使用 sort 需用
using namespace std;
int main()
{
  int i,n, a[10000];
  cin >> n ;
  for(i=0; i<n; ++i)  cin >> a[i];    // 讀入 a 陣列
  sort(a,a+n);                       // 將 a 陣列由小至大排序
// 計算連續相同的數字
  int ans = 1;
  for(i=1;i<n-1;++i)
  {
if( a[i] == a[i-ans] ) ++ ans;
// 當ans為1 若a[i]與前a[i-1]相同,則 ans+1就是長度為2
// 當ans為2 若a[i]與前a[i-2]相同,則 ans+1就是長度為3
// 當ans為 k 若a[i]與前a[i-k]相同,則 ans+1就是長度為 K+1
      //  若沒有比 k 長的相同數字, ans 不會再加
  }
cout << "最多相同數共 " << ans << "個\n";
  return 0;
}
/*
範例輸入
10
1 2 3 4 5 2 3 4 5 2
範例輸出
3
*/