【1024程序员节】技术对抗赛“算法与安全答题”算法题解析
1024程序员节活动结束啦，在技术对抗赛模块中，科技汪邀请了几位程序员UP主为大家出了几道算法题，你答对了吗？ 一起来看看答案解析，体会代码的魅力～
1. 有一根长27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离，求所有蚂蚁都离开木杆的最短时间和最长时间。（本题由UP主@IT私塾提供）
正确答案：11；24
答案解析：
首先对蚂蚁的运动情况进行分析。当两个蚂蚁碰头的时候，会发生怎样的情况？
从图中可以分析出，虽然两个蚂蚁相遇后是掉头往反向走，但是，可以“看作”是两个蚂蚁相遇后，擦肩而过。也就是说，可以认为蚂蚁的运动是独立的，是否有碰头并不是问题的重点。
这样，虽然每个蚂蚁运动的轨迹都与原来不一样了，但所有蚂蚁离开木杆的最短时间和最长时间是不变的。只需分别计算每个蚂蚁离开木杆的时间，即可求出所有蚂蚁离开木杆的时间。
这样，程序只需遍历所有蚂蚁，把每个蚂蚁走出木杆的最长时间（蚂蚁向离自己较远的一端走去），最短时间（蚂蚁向离自己较近的一端走去）分别求出来，得到最大值，就是所有蚂蚁离开木杆的最短时间和最长时间。
伪代码如下：
2. 半仙君和粉丝两人打赌，每人喊1-3中的一个数，谁先喊到30谁赢，请问先喊几有稳赢的可能性？（本题由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("第一个人无必赢策略");
return;
}
Integer pair = scope;
System.out.println("第一个人必赢策略: 第一次喊: " + res.toString() + "，之后每一次喊 （" + pair.toString() + "-对手喊的数） ，直至最终结果。");
return;
}
}
3. 共有N瓶药和4个老鼠，其中只有一瓶毒药，老鼠吃了1天就挂了，现在仅有1天的时间让你找出毒药（每瓶药水都要由老鼠实验喔），请问N最多等于几？（本题由UP主@半仙君_提供）
正确答案：15瓶药
答案解析：
给15个药瓶二进制编号： （2的4次方-1，因为每个老鼠都要吃到药，所以排除0000）
0001、0010、0011、0100、0101、0110、0111、1000、1001、1010、1011、1100、1101、1110、1111
将4个老鼠编号，1号老鼠、2号老鼠、3号老鼠、4号老鼠，分别对应每个药瓶编号位置，把药瓶的药给对应位置的老鼠吃，比如1001号药瓶中第1位和第4位有1，则给1号老鼠和4号老鼠吃，如果老鼠死了，则代表这个药有毒。
4. 香钟（又名火绳钟）是一种使用燃烧香计时的方法，采用榆树皮粉加入少量秸秆和自然元素，配合一定比例的水搅拌均匀后倒模制成香，根据倒模出不同长度、粗细的香，经过燃烧测量可以生产出各种单位时间的计时香，例如辰香（2小时），刻香（15分钟）等。
土堡会战中，上将军安排左右前卫营于丑时出发，约定出发后5刻（1小时15分）分别从敌人大本营西侧与北侧奇袭敌营。营中刻香由于保管不当尽毁，目前营中只有辰香，且辰香不能折断也无法均匀分割，作为左前卫营行军参谋的你要拿出具体的计时方案。请问要想确定出5刻的时长，至少需要多少根辰香？（本题由UP主@黑马程序员提供）
正确答案：4根
答案解析：
目前一根香2小时才能燃烧完，而最终目标是1小时15分，由于不能切割，理论上来说只有让香的燃烧速度加快才能使燃烧时间变短。通常燃烧香的方式是点燃一端，另一端插入香炉中，但是并没有约束香不能两端一起点燃，所以两端点燃香是解决问题的主要思路。
由于最终目标是1小时15分钟，可以拆解成两种完成思路。A.1小时+15分钟，B.完整的1小时15分钟。两种思路都是可以尝试的目标
一根香从两端点燃，燃烧总时间变成了1小时，但是15分钟还是无法确认，因此仅依赖一根香是很难解决这个问题的，需要使用更多的香：
准备ABCD4根香，ABC点燃左端，A点燃右端；
由于A两端均点燃，A经过一小时燃烧完毕，此时B,C燃烧一半（剩余1小时），此时B点燃右端；
由于B两端均点燃，B又经过半小时燃烧完毕，此时C燃烧3/4（剩余半小时），此时C点燃右端；
由于C两端均点燃，C需要15分钟就燃烧完毕了，至此从C点燃右端开始计时到燃烧完毕就可以确认出15分钟时间；
C燃烧完毕后，马上点燃D左右两端，又可以确认出一个1小时，这样就可以得到1小时15分钟。
5. 电视剧《征服》于 2003-03-18 上映，在第九集中，刘华强将卖瓜商贩捅伤，假设捅人剧情发生在 2003-03-26 日，问卖瓜商贩距今 2021-10-24 ，已经被捅了多少天？（本题由UP主@Jack-Cui提供）
正确答案：6787天
答案解析：
方法1:
这里我们运用 Python 里面内置模块 time 来处理问题。
已知2个日期，格式为 yyyy-mm-dd
通过 time.strptime() 方法，把日期时间字符串解析为时间元组
通过 time.mktime() 方法，把时间元祖转换为时间戳
根据2个日期对应的时间戳，得到2个日期相差的秒数，进而计算出间隔天数
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("两个日期的间隔天数：{} ".format(day_diff))
方法2:
这里我们不使用 时间函数 来处理问题，我们可以先计算出每个日期距离公元元年1月1日的总天数，再求出两个日期的间隔天数。
需要判断某个年份是不是闰年，如果是闰年，则该年份天数为365+1。
通过一个列表来存储每月份的天数，如果所给的2个日期中，年份是闰年，则2月份天数为28+1。
根据所给的日期，遍历年月日，分别计算出2个日期距离公元元年1月1日的总天数。
两个总天数相减，即可求出两个日期之间的天数。
注意，闰年的计算方法是 "四年一闰，百年不闰，四百年再闰" ，也就是说一般有以下两个条件：
能被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("两个日期的间隔天数：{} ".format(day_diff))
6. 狸子找了一名粉丝做游戏，初始每人财富相等，每轮游戏中每个人都要付1元随机（等概率）给两人中的一人，记每轮游戏后最富和最穷玩家的差距为x（每个人的财富不设上下限），则在足够多的n轮游戏后，以下描述正确的是？(本题由UP主@狸子LePtC提供）
正确答案：x正比于根号n增加
答案解析：
如果这题问最穷或最富者的钱数x随n的变化，那么大家就会发现这是熟悉的随机游走问题，结论是游走距离正比于跟号n，那么问贫富差距结论当然也是正比于根号n。
7. 一个小孩练习爬台阶，一共10级台阶，小孩可以一次向上选择爬1-3级。但是第3级和第6级台阶被施加了魔法，小孩一旦踏上就会停下来就开始跳《新宝岛》。那么，不让小孩跳《新宝岛》的爬法一共有多少种？（本题由UP主@魔法小分队队长提供）
正确答案：42
答案解析：
这道题我们设 f(n)为爬上第n级时，爬法的总数。令f(0)=1，那么f(1) = 1因为爬一级台阶只有一种爬法，爬两级台阶一共有两种爬法，f(n) = f(n-1) + f(n-2) + f(n-3) (n>=3)， 这里要注意当n=3或6时f(n)=0，因此从1到10级台阶的爬法总数分别为“1,2,0,3,5,0,8,13,21,42”，因此答案是42。
8. 计算100到10000（包含10000）所有偶数相加结果。（本题由UP主@python学习者提供）
正确答案：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("期间所有偶数之和: " + "0");
return;
} else if (end == begin){
if (end%2==0){
System.out.println("期间所有偶数之和: " + end.toString());
return;
} else {
System.out.println("期间所有偶数之和: " + "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("期间所有偶数之和: " + res.toString());
return;
}
}
9. 期末考试结束了，老师决定带学生们去卷饼店吃烤鸭饼。老师看到大饼和鸭子，搞了一个活动：每人可以拿走一张饼，谁卷到的食物美味程度总和最高，谁就能获得称号：卷王之王！Vita很想得到“卷王之王”称号，他的大饼可以装下大小总和不超过500的食物，现在有7块鸭肉和6根黄瓜，每份食物都有它的大小和美味程度。
每块鸭肉的大小：85、86、73、66、114、51、99
每块鸭肉的美味程度：71、103、44、87、112、78、36
每根黄瓜的大小：35、44、27、41、65、38
每块黄瓜的美味程度：41、46、13、74、71、27
老师要求大饼里至少有一块鸭肉和一根黄瓜。请问，Vita卷到的食物美味程度总和最大是多少？（本题由UP主@小学生Vita君提供）
正确答案：593
答案解析：
一开始你可能会尝试这样做：把每块鸭肉和每块黄瓜都算出性价比（美味程度÷大小），然后对性价比从高到低排序，先选出性价比最高的1块鸭肉和1块黄瓜，再根据排序结果依次选择后面的食材：如果大饼还能装，就把它放入大饼；如果大饼装不下了，就跳过，看下一个，直到看完所有食物为止。
按照这样的选法，我们来计算一下结果：
【美味程度】584
【大小】500
最终的结果是584，并且大饼正好装满。Amazing啊！
但是，没有比它更好的装法吗？NO！
只要你学过动态规划算法，就会发现这是一个01背包问题。
01背包问题就是有n个物品（鸭肉和黄瓜），每个物品都有它的重量（大小）和价值（美味程度），背包的容量（大饼的容量）是t，你可以选择一些物品放进背包里，求在所选物品重量总和不超过t时，最大的价值总和是多少。
我们可以用数组f[i][j]记录当有前i个物品，当前背包剩余容量为j时，能取得的最大价值。每件物品的重量为w[i]，价值为v[i]。我们用两层循环，第一层枚举每一件物品，第二层枚举剩余容量。每次枚举到一个剩余容量，都有两种选择：第一是把这个物品放入背包，第二是不放进背包。选择放进背包的前提是背包有足够的容量装下这件物品，否则只能不装。放进背包时，可以取得的价值是f[i][j]=f[i-1][j-w[i]]+v[i]。不放进背包，可以取得的价值是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]; //当前物品装不下
else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); //当前物品选或不选，取最大价值
}
}
cout << f[n][t];
这道题要求至少要装一块鸭肉和一根黄瓜，所以装鸭肉和装黄瓜就是两个01背包：背包f1装鸭肉，背包f2装黄瓜。
最终我们要求两个背包大小总和为500，所以我们在枚举最终结果时，需要枚举两个背包总容量为500的所有组合，即：如果j是大饼中鸭肉的总大小，那么500-j就是大饼中黄瓜的总大小。注意，为了保证鸭肉和黄瓜都有，我们可以利用背包的一个特性：如果规定容量下至少能选择一个物品，则背包的价值一定大于0。所以，只要背包f1的第j项和背包f2的第500-j项都大于0，就代表鸭肉和黄瓜一定都至少有一块。
通过动态规划算法，我们可以得到一个更好的方案：
【美味程度】593
【大小】496
所以正确答案是593。
C++代码：
#include <iostream>
using namespace std;
//数据初始化
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]);
}
}
//枚举两个背包的组合
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]);
}
}
//输出结果
cout << ans;
}
10. 现有5个元素，它们各不相同，且两两之间可比较。我们可以通过反复比较两个元素的大小，来找出5个元素中的中位数。请问最少用多少次比较，可以确保总能找到 5个元素的中位数?（本题由UP主@算法主义提供）
正确答案：6次
答案解析：
点击此处，查看活动详情
