计算思维引导 陶先平 南京大学计算机软件研究所
计算思维引导 陶先平 南京大学计算机软件研究所
找假币--何谓“计算思维”？ 给你70个外观完全一样的金币，但是你知道 其中有一个是假币，其重量比真币轻。给你 一架没有砝码的天平，你可以在天平两边 摆任意多个金币，比较他们的轻重。 •请设计一种方法，通过若干次称量，确定 哪一个是假币
找假币---何谓“计算思维”？ •给你70个外观完全一样的金币,但是你知道 其中有一个是假币,其重量比真币轻。给你 一架没有砝码的天平，你可以在天平两边 摆任意多个金币，比较他们的轻重。 •请设计一种方法，通过若干次称量，确定 哪一个是假币
第一个解法 总共称7次 w 雨平分称量。 ·将轻的一侧钙个加性意一个再平分称量。 ·将轻的一侧的3个加另外任意一个再平分称量。 ·将轻的一侧的2个分别放到天平两边，轻的是假币。完成
第一个解法 • 先将70个金币平均分两份，放到天平两边。 假币必在轻的那一侧的35个中。 • 将那35个加上另一侧中任意一个，再平分称量。 • 将轻的一侧的18个平分再称量。 • 将轻的一侧的9个加另外任意一个再平分称量。 • 将轻的一侧的5个加另外任意一个再平分称量。 • 将轻的一侧的3个加另外任意一个再平分称量。 • 将轻的一侧的2个分别放到天平两边，轻的是假币。完成 总共称7次
第一个解法稍稍改进 总共称6次 ·先将70个金币平均分两份，放到天平两边。 ·将那35个中红意个放穷，其金歌色益。 每边17个。 广年家的个中任个皮咨 香的二侧的8个平分再称量，每 边4个 但花 还能5 ·将轻的一侧的4个再平分标量，每边2个。 ·将轻的一侧的2个再平分称量，每边个。轻的是假币。完成
第一个解法稍稍改进 • 先将70个金币平均分两份，放到天平两边。 假币必在轻的那一侧的35个中。 • 将那35个中任意一个放一旁，其余再平分称量，每边17个。 • 若相等则旁边的是假币，否则将轻的一侧的17个中任意一个放旁 边，其余的再平分再称量，每边8个。 • 若相等则旁边的是假币，否则将轻的一侧的8个平分再称量，每 边4个 • 将轻的一侧的4个再平分称量，每边2个。 • 将轻的一侧的2个再平分称量，每边个。轻的是假币。完成 总共称6次
一个更好的办法 [1.23[24.46] 但遮东还的具、 [1.819.16] [24.31[32.40] [55.57[58.601 [47:[48] 1531:[54] 50]:[51] 称四次！
一个更好的办法 [1..23]:[24..46] [1..8]:[9..16] [47..54]:[55..62] [24..31]:[32..40] < = > ...... ...... [47..49]:[50..52] [63..65]:[66..68] [55..57]:[58..60] [47]:[48] [53]:[54] [50]:[51] ...... 称四次！