1024程序員節(jié)活動(dòng)結(jié)束啦，在技術(shù)對(duì)抗賽模塊中，科技汪邀請(qǐng)了幾位程序員UP主為大家出了幾道算法題，你答對(duì)了嗎？ 一起來看看答案解析，體會(huì)代碼的魅力～

1.?有一根長(zhǎng)27厘米的細(xì)木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個(gè)位置上各有一只螞蟻。木桿很細(xì)，不能同時(shí)通過兩只螞蟻。開始時(shí)，螞蟻的頭朝左還是朝右是任意的，它們只會(huì)朝前走或調(diào)頭，但不會(huì)后退。當(dāng)任意兩只螞蟻碰頭時(shí)，兩只螞蟻會(huì)同時(shí)調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離，求所有螞蟻都離開木桿的最短時(shí)間和最長(zhǎng)時(shí)間。（本題由UP主@IT私塾提供）

正確答案：11；24

答案解析：

首先對(duì)螞蟻的運(yùn)動(dòng)情況進(jìn)行分析。當(dāng)兩個(gè)螞蟻碰頭的時(shí)候，會(huì)發(fā)生怎樣的情況？

從圖中可以分析出，雖然兩個(gè)螞蟻相遇后是掉頭往反向走，但是，可以“看作”是兩個(gè)螞蟻相遇后，擦肩而過。也就是說，可以認(rèn)為螞蟻的運(yùn)動(dòng)是獨(dú)立的，是否有碰頭并不是問題的重點(diǎn)。

這樣，雖然每個(gè)螞蟻運(yùn)動(dòng)的軌跡都與原來不一樣了，但所有螞蟻離開木桿的最短時(shí)間和最長(zhǎng)時(shí)間是不變的。只需分別計(jì)算每個(gè)螞蟻離開木桿的時(shí)間，即可求出所有螞蟻離開木桿的時(shí)間。

這樣，程序只需遍歷所有螞蟻，把每個(gè)螞蟻?zhàn)叱瞿緱U的最長(zhǎng)時(shí)間（螞蟻向離自己較遠(yuǎn)的一端走去），最短時(shí)間（螞蟻向離自己較近的一端走去）分別求出來，得到最大值，就是所有螞蟻離開木桿的最短時(shí)間和最長(zhǎng)時(shí)間。

偽代碼如下：

2.?半仙君和粉絲兩人打賭，每人喊1-3中的一個(gè)數(shù)，誰先喊到30誰贏，請(qǐng)問先喊幾有穩(wěn)贏的可能性？（本題由UP主@半仙君_提供）

正確答案：2

答案解析：

30 % (1 + 3) = 2

編程：

import java.util.*;

public class FirstDemo {

? ?public static void main(String args[]) {

Random rand = new Random();

Integer terminal = rand.nextInt(10000) + 1;

System.out.println("終止值: " + terminal.toString());

Integer scope = rand.nextInt(100) + 1;

System.out.println("范圍值: 1-" + scope.toString());

Integer res = terminal % scope;

if (res == 0) {

?System.out.println("第一個(gè)人無必贏策略");

return;

}

Integer pair = scope;

System.out.println("第一個(gè)人必贏策略: 第一次喊: " + res.toString() + "，之后每一次喊 （" + pair.toString() + "-對(duì)手喊的數(shù)） ，直至最終結(jié)果。");

return;

}

}

3. 共有N瓶藥和4個(gè)老鼠，其中只有一瓶毒藥，老鼠吃了1天就掛了，現(xiàn)在僅有1天的時(shí)間讓你找出毒藥（每瓶藥水都要由老鼠實(shí)驗(yàn)喔），請(qǐng)問N最多等于幾？（本題由UP主@半仙君_提供）

正確答案：15瓶藥?

答案解析：

給15個(gè)藥瓶二進(jìn)制編號(hào)： （2的4次方-1，因?yàn)槊總€(gè)老鼠都要吃到藥，所以排除0000）

0001、0010、0011、0100、0101、0110、0111、1000、1001、1010、1011、1100、1101、1110、1111

將4個(gè)老鼠編號(hào)，1號(hào)老鼠、2號(hào)老鼠、3號(hào)老鼠、4號(hào)老鼠，分別對(duì)應(yīng)每個(gè)藥瓶編號(hào)位置，把藥瓶的藥給對(duì)應(yīng)位置的老鼠吃，比如1001號(hào)藥瓶中第1位和第4位有1，則給1號(hào)老鼠和4號(hào)老鼠吃，如果老鼠死了，則代表這個(gè)藥有毒。

4. 香鐘（又名火繩鐘）是一種使用燃燒香計(jì)時(shí)的方法，采用榆樹皮粉加入少量秸稈和自然元素，配合一定比例的水?dāng)嚢杈鶆蚝蟮鼓Ｖ瞥上?，根?jù)倒模出不同長(zhǎng)度、粗細(xì)的香，經(jīng)過燃燒測(cè)量可以生產(chǎn)出各種單位時(shí)間的計(jì)時(shí)香，例如辰香（2小時(shí)），刻香（15分鐘）等。

土堡會(huì)戰(zhàn)中，上將軍安排左右前衛(wèi)營于丑時(shí)出發(fā)，約定出發(fā)后5刻（1小時(shí)15分）分別從敵人大本營西側(cè)與北側(cè)奇襲敵營。營中刻香由于保管不當(dāng)盡毀，目前營中只有辰香，且辰香不能折斷也無法均勻分割，作為左前衛(wèi)營行軍參謀的你要拿出具體的計(jì)時(shí)方案。請(qǐng)問要想確定出5刻的時(shí)長(zhǎng)，至少需要多少根辰香？（本題由UP主@黑馬程序員提供）

正確答案：4根

答案解析：

目前一根香2小時(shí)才能燃燒完，而最終目標(biāo)是1小時(shí)15分，由于不能切割，理論上來說只有讓香的燃燒速度加快才能使燃燒時(shí)間變短。通常燃燒香的方式是點(diǎn)燃一端，另一端插入香爐中，但是并沒有約束香不能兩端一起點(diǎn)燃，所以兩端點(diǎn)燃香是解決問題的主要思路。

由于最終目標(biāo)是1小時(shí)15分鐘，可以拆解成兩種完成思路。A.1小時(shí)+15分鐘，B.完整的1小時(shí)15分鐘。兩種思路都是可以嘗試的目標(biāo)

一根香從兩端點(diǎn)燃，燃燒總時(shí)間變成了1小時(shí)，但是15分鐘還是無法確認(rèn)，因此僅依賴一根香是很難解決這個(gè)問題的，需要使用更多的香：

準(zhǔn)備ABCD4根香，ABC點(diǎn)燃左端，A點(diǎn)燃右端；

由于A兩端均點(diǎn)燃，A經(jīng)過一小時(shí)燃燒完畢，此時(shí)B,C燃燒一半（剩余1小時(shí)），此時(shí)B點(diǎn)燃右端；

由于B兩端均點(diǎn)燃，B又經(jīng)過半小時(shí)燃燒完畢，此時(shí)C燃燒3/4（剩余半小時(shí)），此時(shí)C點(diǎn)燃右端；

由于C兩端均點(diǎn)燃，C需要15分鐘就燃燒完畢了，至此從C點(diǎn)燃右端開始計(jì)時(shí)到燃燒完畢就可以確認(rèn)出15分鐘時(shí)間；

C燃燒完畢后，馬上點(diǎn)燃D左右兩端，又可以確認(rèn)出一個(gè)1小時(shí)，這樣就可以得到1小時(shí)15分鐘。

5.?電視劇《征服》于 2003-03-18 上映，在第九集中，劉華強(qiáng)將賣瓜商販捅傷，假設(shè)捅人劇情發(fā)生在 2003-03-26 日，問賣瓜商販距今 2021-10-24 ，已經(jīng)被捅了多少天？（本題由UP主@Jack-Cui提供）

正確答案：6787天

答案解析：

方法1:

這里我們運(yùn)用 Python 里面內(nèi)置模塊 time 來處理問題。

已知2個(gè)日期，格式為 yyyy-mm-dd

通過 time.strptime() 方法，把日期時(shí)間字符串解析為時(shí)間元組

通過 time.mktime() 方法，把時(shí)間元祖轉(zhuǎn)換為時(shí)間戳

根據(jù)2個(gè)日期對(duì)應(yīng)的時(shí)間戳，得到2個(gè)日期相差的秒數(shù)，進(jìn)而計(jì)算出間隔天數(shù)

import time

def demo(day1, day2):

? ?time_array1 = time.strptime(day1, "%Y-%m-%d")

? ?timestamp_day1 = int(time.mktime(time_array1))

? ?time_array2 = time.strptime(day2, "%Y-%m-%d")

? ?timestamp_day2 = int(time.mktime(time_array2))

? ?result = (timestamp_day2 - timestamp_day1) // 60 // 60 // 24

? ?return result

day1 = "2003-03-26"

day2 = "2021-10-24"

day_diff = demo(day1, day2)

print("兩個(gè)日期的間隔天數(shù)：{} ".format(day_diff))

方法2:

這里我們不使用 時(shí)間函數(shù) 來處理問題，我們可以先計(jì)算出每個(gè)日期距離公元元年1月1日的總天數(shù)，再求出兩個(gè)日期的間隔天數(shù)。

需要判斷某個(gè)年份是不是閏年，如果是閏年，則該年份天數(shù)為365+1。

通過一個(gè)列表來存儲(chǔ)每月份的天數(shù)，如果所給的2個(gè)日期中，年份是閏年，則2月份天數(shù)為28+1。

根據(jù)所給的日期，遍歷年月日，分別計(jì)算出2個(gè)日期距離公元元年1月1日的總天數(shù)。

兩個(gè)總天數(shù)相減，即可求出兩個(gè)日期之間的天數(shù)。

注意，閏年的計(jì)算方法是 "四年一閏，百年不閏，四百年再閏" ，也就是說一般有以下兩個(gè)條件：

能被4整除且不能被100整除的是閏年

能被400整除的是閏年

def is_leap_year(year):

? ?if (year % 4 == 0 and year % 100 != 0) or year % 400 == 0:

? ? ? ?return 1

? ?else:

? ? ? ?return 0

def get_days(year, month, day):

? ?days = 0

? ?month_days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

? ?if is_leap_year(year):

? ? ? ?month_days[1] = 29

? ?for i in range(1, year):

? ? ? ?year_day = 365

? ? ? ?if is_leap_year(i):

? ? ? ? ? ?year_day = 366

? ? ? ?days += year_day

? ?for m in range(month - 1):

? ? ? ?days += month_days[m]

? ?days += day

? ?return days

def get_result(start_time, end_time):

? ?res = end_time - start_time

? ?return res

day1 = "2003-03-26"

day2 = "2021-10-24"

year1, month1, day1 = list(map(lambda x:int(x), day1.split("-")))

year2, month2, day2 = list(map(lambda x:int(x), day2.split("-")))

days1 = get_days(year1, month1, day1)

days2 = get_days(year2, month2, day2)

day_diff = get_result(days1, days2)

print("兩個(gè)日期的間隔天數(shù)：{} ".format(day_diff))

6. 貍子找了一名粉絲做游戲，初始每人財(cái)富相等，每輪游戲中每個(gè)人都要付1元隨機(jī)（等概率）給兩人中的一人，記每輪游戲后最富和最窮玩家的差距為x（每個(gè)人的財(cái)富不設(shè)上下限），則在足夠多的n輪游戲后，以下描述正確的是？(本題由UP主@貍子LePtC提供）

正確答案：x正比于根號(hào)n增加

答案解析：

如果這題問最窮或最富者的錢數(shù)x隨n的變化，那么大家就會(huì)發(fā)現(xiàn)這是熟悉的隨機(jī)游走問題，結(jié)論是游走距離正比于跟號(hào)n，那么問貧富差距結(jié)論當(dāng)然也是正比于根號(hào)n。

7.?一個(gè)小孩練習(xí)爬臺(tái)階，一共10級(jí)臺(tái)階，小孩可以一次向上選擇爬1-3級(jí)。但是第3級(jí)和第6級(jí)臺(tái)階被施加了魔法，小孩一旦踏上就會(huì)停下來就開始跳《新寶島》。那么，不讓小孩跳《新寶島》的爬法一共有多少種？（本題由UP主@魔法小分隊(duì)隊(duì)長(zhǎng)提供）

正確答案：42

答案解析：

這道題我們?cè)O(shè) f(n)為爬上第n級(jí)時(shí)，爬法的總數(shù)。令f(0)=1，那么f(1) = 1因?yàn)榕酪患?jí)臺(tái)階只有一種爬法，爬兩級(jí)臺(tái)階一共有兩種爬法，f(n) = f(n-1) + f(n-2) + f(n-3) ?(n>=3)， 這里要注意當(dāng)n=3或6時(shí)f(n)=0，因此從1到10級(jí)臺(tái)階的爬法總數(shù)分別為“1,2,0,3,5,0,8,13,21,42”，因此答案是42。

8.?計(jì)算100到10000（包含10000）所有偶數(shù)相加結(jié)果。（本題由UP主@python學(xué)習(xí)者提供）

正確答案：25002550

答案解析：

總和 =（9999+100）*（9999-100+1）/2

答案 =（總和-（9999-100+1）/2）/2 ?+10000

編程：

import java.util.*;

public class SumDataDemo {

? ?static Integer sumAllNum(int begin, int end) {

return (begin+end)*(end-begin+1)/2;

? ?}

? ?static Integer sumEvenNumber(int sumNum, int begin, int end) {

Integer res = 0;

Integer delta = (end - begin + 1) / 2;

if (begin % 2 == 0) {

res = (sumNum - delta) / 2;

} else {

res = (sumNum + delta) / 2;

}

return res;

? ?}

? ?public static void main(String args[]) {

Random rand = new Random();

Integer begin = rand.nextInt(10000);

System.out.println("起始值: " + begin.toString());

Integer end = rand.nextInt(10000);

System.out.println("終止值: " + end.toString());

if (end < begin){

System.out.println("期間所有偶數(shù)之和: " + "0");

return;

} else if (end == begin){

if (end%2==0){

System.out.println("期間所有偶數(shù)之和: " + end.toString());

return;

} else {

System.out.println("期間所有偶數(shù)之和: " + "0");

return;

}

}

Integer res = 0;

Integer sumAll = 0;

Integer ifUnEven = (end - begin + 1) % 2;

if (ifUnEven == 1) {

end = end - 1;

sumAll = sumAllNum(begin, end);

res = sumEvenNumber(sumAll, begin, end);

Integer endIfUnEven = (end + 1) % 2;

if (endIfUnEven == 0) {

res = res + end + 1;

}

} else {

sumAll = sumAllNum(begin, end);

res = sumEvenNumber(sumAll, begin, end);

}

System.out.println("期間所有偶數(shù)之和: " + res.toString());

return;

? ?}

}

9. 期末考試結(jié)束了，老師決定帶學(xué)生們?nèi)ゾ盹灥瓿钥绝嗭?。老師看到大餅和鴨子，搞了一個(gè)活動(dòng)：每人可以拿走一張餅，誰卷到的食物美味程度總和最高，誰就能獲得稱號(hào)：卷王之王！Vita很想得到“卷王之王”稱號(hào)，他的大餅可以裝下大小總和不超過500的食物，現(xiàn)在有7塊鴨肉和6根黃瓜，每份食物都有它的大小和美味程度。

每塊鴨肉的大?。?5、86、73、66、114、51、99

每塊鴨肉的美味程度：71、103、44、87、112、78、36

每根黃瓜的大?。?5、44、27、41、65、38

每塊黃瓜的美味程度：41、46、13、74、71、27

老師要求大餅里至少有一塊鴨肉和一根黃瓜。請(qǐng)問，Vita卷到的食物美味程度總和最大是多少？（本題由UP主@小學(xué)生Vita君提供）

正確答案：593

答案解析：

一開始你可能會(huì)嘗試這樣做：把每塊鴨肉和每塊黃瓜都算出性價(jià)比（美味程度÷大?。?，然后對(duì)性價(jià)比從高到低排序，先選出性價(jià)比最高的1塊鴨肉和1塊黃瓜，再根據(jù)排序結(jié)果依次選擇后面的食材：如果大餅還能裝，就把它放入大餅；如果大餅裝不下了，就跳過，看下一個(gè)，直到看完所有食物為止。

按照這樣的選法，我們來計(jì)算一下結(jié)果：

【美味程度】584

【大小】500

最終的結(jié)果是584，并且大餅正好裝滿。Amazing啊！

但是，沒有比它更好的裝法嗎？NO！

只要你學(xué)過動(dòng)態(tài)規(guī)劃算法，就會(huì)發(fā)現(xiàn)這是一個(gè)01背包問題。

01背包問題就是有n個(gè)物品（鴨肉和黃瓜），每個(gè)物品都有它的重量（大?。┖蛢r(jià)值（美味程度），背包的容量（大餅的容量）是t，你可以選擇一些物品放進(jìn)背包里，求在所選物品重量總和不超過t時(shí)，最大的價(jià)值總和是多少。

我們可以用數(shù)組f[i][j]記錄當(dāng)有前i個(gè)物品，當(dāng)前背包剩余容量為j時(shí)，能取得的最大價(jià)值。每件物品的重量為w[i]，價(jià)值為v[i]。我們用兩層循環(huán)，第一層枚舉每一件物品，第二層枚舉剩余容量。每次枚舉到一個(gè)剩余容量，都有兩種選擇：第一是把這個(gè)物品放入背包，第二是不放進(jìn)背包。選擇放進(jìn)背包的前提是背包有足夠的容量裝下這件物品，否則只能不裝。放進(jìn)背包時(shí)，可以取得的價(jià)值是f[i][j]=f[i-1][j-w[i]]+v[i]。不放進(jìn)背包，可以取得的價(jià)值是f[i][j]=f[i-1][j]。上代碼！

for (int i=1;i<=n;i++) {

for (int j=0;j<=t;j+++) {

if (j<w[i]) f[i][j]=f[i-1][j]; //當(dāng)前物品裝不下

else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); //當(dāng)前物品選或不選，取最大價(jià)值

}

}

cout << f[n][t];

這道題要求至少要裝一塊鴨肉和一根黃瓜，所以裝鴨肉和裝黃瓜就是兩個(gè)01背包：背包f1裝鴨肉，背包f2裝黃瓜。

最終我們要求兩個(gè)背包大小總和為500，所以我們?cè)诿杜e最終結(jié)果時(shí)，需要枚舉兩個(gè)背包總?cè)萘繛?00的所有組合，即：如果j是大餅中鴨肉的總大小，那么500-j就是大餅中黃瓜的總大小。注意，為了保證鴨肉和黃瓜都有，我們可以利用背包的一個(gè)特性：如果規(guī)定容量下至少能選擇一個(gè)物品，則背包的價(jià)值一定大于0。所以，只要背包f1的第j項(xiàng)和背包f2的第500-j項(xiàng)都大于0，就代表鴨肉和黃瓜一定都至少有一塊。

通過動(dòng)態(tài)規(guī)劃算法，我們可以得到一個(gè)更好的方案：

【美味程度】593

【大小】496

所以正確答案是593。

C++代碼：

#include <iostream>

using namespace std;

//數(shù)據(jù)初始化

const int n=7,m=6,t=500;

int w1[]={0,85,86,73,66,114,51,99};

int v1[]={0,71,103,44,87,112,78,36};

int w2[]={0,35,44,27,41,65,38};

int v2[]={0,41,46,13,74,71,27};

int f1[10][505],f2[10][505],ans;

int main() {

//鴨肉的背包

? ?for (int i=1;i<=n;i++) {

? ? ? ?for (int j=0;j<=t;j++) {

? ? ? ? ? ?if (j<w1[i]) f1[i][j]=f1[i-1][j];

? ? ? ? ? ?else f1[i][j]=max(f1[i-1][j],f1[i-1][j-w1[i]]+v1[i]);

? ? ? ?}

? ?}

//黃瓜的背包

? ?for (int i=1;i<=m;i++) {

? ? ? ?for (int j=0;j<=t;j++) {

? ? ? ? ? ?if (j<w2[i]) f2[i][j]=f2[i-1][j];

? ? ? ? ? ?else f2[i][j]=max(f2[i-1][j],f2[i-1][j-w2[i]]+v2[i]);

? ? ? ?}

? ?}

//枚舉兩個(gè)背包的組合

? ?for (int j=0;j<=t;j++) {

? ? ? ?if (f1[n][j]>0&&f2[m][t-j]>0) { //鴨肉和黃瓜都要有

? ? ? ? ? ?ans=max(ans,f1[n][j]+f2[m][t-j]);

? ? ? ?}

? ?}

//輸出結(jié)果

? ?cout << ans;

}

10. 現(xiàn)有5個(gè)元素，它們各不相同，且兩兩之間可比較。我們可以通過反復(fù)比較兩個(gè)元素的大小，來找出5個(gè)元素中的中位數(shù)。請(qǐng)問最少用多少次比較，可以確?？偰苷业?5個(gè)元素的中位數(shù)?（本題由UP主@算法主義提供）

正確答案：6次

答案解析：

點(diǎn)擊此處，查看活動(dòng)詳情