連續和的平方數—排列的個數—巧放棋子—取中間數字—去掉重復字母—日歷天數之差
①連續和的平方數
1+3 = 4, ?1+3+5 = 9, ?1+3+5+7 = 16 它們的結果都是平方數。
這是偶然的巧合嗎?下面代碼驗證對于累加至1000以內的情況都成立。
~~~
int n = 1;
for(int i=1; i<1000/2; i++)
{
n += 2 * i + 1;
int m = ______________;
if( m * m != n)
{
printf("加至%d 時不成立!\n", 2 * i + 1);
break;
}
}
~~~
連續和的平方數,我剛開始還在那找規律,發現 n最后加上的數字再加1 再除以2 所得到的數的平方就是最后那個平方數, 化簡下來: (2*i+1+1)/2=i+1 ? 然后突然發現我二了= 。=
答案:i+1
②排列的個數
計算3個A,2個B可以組成多少種排列的問題(如:AAABB, AABBA)是《組合數學》的研究領域。
但有些情況下,也可以利用計算機計算速度快的特點通過巧妙的推理來解決問題。
下列的程序計算了m個A,n個B可以組合成多少個不同排列的問題。
~~~
int f(int m, int n)
{
if(m==0 || n==0) return 1;
return _______________________;
}
~~~
這道題,一看就知道遞歸題目了,做了這么多代碼填空題我也發現了,看見只給一個函數,最上面還有一些判斷,return的,一般跑不了遞歸。在本上畫一畫,算一算,不難求出來。
答案: f(m-1,n)+f(m,n-1)
③巧放棋子
今有 6 x 6 的棋盤格。其中某些格子已經預先放好了棋子。
現在要再放上去一些,使得:每行每列都正好有3顆棋子。
我們希望推算出所有可能的放法。

? 初始數組中,“1”表示放有棋子,“0”表示空白。 ? ?
~~~
int N = 0;
bool CheckStoneNum(int x[][6])
{
for(int k=0; k<6; k++)
{
int NumRow = 0;
int NumCol = 0;
for(int i=0; i<6; i++)
{
if(x[k][i]) NumRow++;
if(x[i][k]) NumCol++;
}
if(_____________________) return false; // 填空
}
return true;
}
int GetRowStoneNum(int x[][6], int r)
{
int sum = 0;
for(int i=0; i<6; i++) if(x[r][i]) sum++;
return sum;
}
int GetColStoneNum(int x[][6], int c)
{
int sum = 0;
for(int i=0; i<6; i++) if(x[i][c]) sum++;
return sum;
}
void show(int x[][6])
{
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++) printf("%2d", x[i][j]);
printf("\n");
}
printf("\n");
}
void f(int x[][6], int r, int c);
void GoNext(int x[][6], int r, int c)
{
if(c<6)
_______________________; // 填空
else
f(x, r+1, 0);
}
void f(int x[][6], int r, int c)
{
if(r==6)
{
if(CheckStoneNum(x))
{
N++;
show(x);
}
return;
}
if(______________) // 已經放有了棋子 // 填空
{
GoNext(x,r,c);
return;
}
int rr = GetRowStoneNum(x,r);
int cc = GetColStoneNum(x,c);
if(cc>=3) // 本列已滿
GoNext(x,r,c);
else if(rr>=3) // 本行已滿
f(x, r+1, 0);
else
{
x[r][c] = 1;
GoNext(x,r,c);
x[r][c] = 0;
if(!(3-rr >= 6-c || 3-cc >= 6-r)) // 本行或本列嚴重缺子,則本格不能空著!
GoNext(x,r,c);
}
}
int main(int argc, char* argv[])
{
int x[6][6] = {
{1,0,0,0,0,0},
{0,0,1,0,1,0},
{0,0,1,1,0,1},
{0,1,0,0,1,0},
{0,0,0,1,0,0},
{1,0,1,0,0,1}
};
f(x, 0, 0);
printf("%d\n", N);
return 0;
}
~~~
這道題代碼不短,莫慌莫急,慢慢縷一縷就很好解決了,
先看最下面的空,后面還有注釋: 本格有棋子,那還用想填什么嗎?當然是當數組內數為1的時候啊。
再看倒數第二個,下面那個else是r+1,然后c歸0,顯然是換行操作,什么時候需要換行?肯定讀到末尾了,
就是c>6的時候。
再看第一個,乍一看,真不懂,回程序找找哪里出現這個函數調用,發現調用這個函數,返回1的時候N自增,
就是棋子的數目增加一個了,那就簡單了,肯定是判斷該行,該列棋子是否都為3了。如果符合這個條件,就
可以放棋子,棋子總數++。
答案:
~~~
NumRow!=3 || NumCol!=3 ? ? ? ? ? ??
f(x, r, c+1) ? ? ? ? ? ? ? ? ? ? ??
x[r][c] ?或 x[r][c]==1 ? ? ? ? ??
~~~
④取中間數字
假設a,b,c是3個互不相等的整數。下列代碼取出它們中居中的數值,記錄在m中。
其中的swap()函數可以交換兩個變量的值。
~~~
if(a>b) swap(&a, &b);
if(b>c) swap(&b, &c);
______________________;
int m = b;
~~~
這題目,很容易理解吧,互不相等的整數,取中間那個,肯定三個數需要兩兩比較,
第一個if進行了a,b 比較,第二個if 進行 b,c比較,
第三個肯定也需要比較一次,是比較a,b呢還是b,c呢?
可以這樣看:
如果a<b, 第一個If沒有執行,b與c比較,b是b,c中小的那個,那么肯定需要再與a比較一次,要去中間的嘛。
如果a>b,第一個if執行,再將b,c比較,b依舊是較小的那個,b,c中較小的再與原來的b即現在的a比較,取中間。
上面的話,是不是很繞啊。。。
就是因為b,c比較在后,肯定無法與a,b中較大的數比較,所以要增設一個a,b比較。
實在不理解可以列幾組數據來算一下。
答案: if(a>b) swap(&a,&b)
⑤去掉重復字母
給定一個串,例如“aabbbcddddkkkmmmmaakkkk”我們希望去掉連續的重復字母,
得出串:“abcdkmak”,下面代碼實現了該功能,請完善之。
~~~
char* p = "aabbbcddddkkkmmmmaakkkk";
char buf[100];
char* q = p;
int i=0;
for(;*q;)
{
if(___________|| *q != *(q-1))
{
buf[i++] = *q;
}
q++;
}
buf[i] = '\0';
printf("%s\n", buf);
~~~
任務明確,代碼完整, 將不重復的字符存到buf數組中,q指向p頭部即a的位置, for循環第一第三條件空缺,判斷q是否等于NULL, 什么情況下 會將指針q的內容賦值給buf呢?if已經寫一半了,就是當當前指針指向的內容不等于之前指針指向的內容的時候,會賦值,這就有一個問題了,如果指針指向第一個位置,怎么辦?所以空缺的地方顯而易見了。
答案:p==q
⑥日歷天數差
人類歷史上出現了很多種歷法。現行的公歷即格里歷由儒略歷改革而來。它是目前較為精確和規則簡明的一種歷法,約3300年誤差一日。因為閏年問題以及每個月的長度不等,仍然使得某些計算較為麻煩。
比如:求兩個日期間差多少天。
下面的代碼實現了求兩個由公歷表示的日期間差多少天的功能。
其計算原理是先求出每個日期距離1年1月1日的天數差值,再進一步做差即可。
請研讀代碼,填寫缺失的部分。
~~~
struct MyDate
{
int year;
int month;
int day;
};
int GetAbsDays(MyDate x)
{
int i;
int month_day[] = {31,28,31,30,31,30,31,31,30,31,30,31};
int year = x.year-1; // 因為欲求距離1年1月1日的距離
int days = year * 365 + year/4 - year/100 + year/400;
if(x.year%4==0 && x.year%100!=0 || x.year%400==0) month_day[1]++;
for(i=0; i<______________; i++)
days += month_day[i];
days += x.day-1;
return days;
}
int GetDiffDays(MyDate a, MyDate b)
{
return GetAbsDays(b) - GetAbsDays(a);
}
int main(int argc, char* argv[])
{
MyDate a = {1842,5,18};
MyDate b = {2000,3,13};
int n = GetDiffDays(a,b);
printf("%d\n", n);
}
~~~
這道題無外乎求,某個日期到1年1月1日的時間,一看到計算年月日的,我就直接看空缺處了,for循環體內是
days+=month_day[i],就是總天數加上該月份擁有的天數,那還用想嗎?肯定填當前月份了,
但是假設日期是 2014年3月22日,月份肯定不能等于3,所以就是x.month-1咯
答案:x.month-1
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費