Python:每日一题之最少砝码
创始人
2024-03-03 13:25:15
0次
问题描述
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
输入格式
输入包含一个正整数 N。
输出格式
输出一个整数代表答案。
样例输入
7
样例输出
3
样例说明
3 个砝码重量是 1、4、6，可以称出 1 至 7的所有重量。
1 = 1；
2 = 6 − 4(天平一边放 6，另一边放 4)；
3 = 4 − 1；
4 = 4；
5 = 6 − 1；
6 = 6；
7 = 1 + 6；
少于 3 个砝码不可能称出 1 至 7 的所有重量。
分析：
- 设当前砝码称重范围是1~R
- 加一个砝码 w ,w 的值远大于 R 且不等于前面已能得到的称重
- 新的称重范围是：1，2，...,R,W-R,W-R+1,...,W,W+1,W+2,...,W+R
- 从R到W-R是连续的，有W-R=R+1,即W=2R+1
- 当前称重范围是1~R,加一个W=2R+1的砝码，可以扩展到新的称重范围R'=W+R=3R+1
表格给出了一种最少砝码的实现方式
| R | 原砝码 | 原称重范围 | W=2R+1 | R'=3R+1 | 新砝码 | 新称重范围 |
| 1 | 1 | 1 | 3 | 4 | 1，3 | 1 ~ 4 |
| 4 | 1，3 | 1 ~ 4 | 9 | 13 | 1，3，9 | 1 ~13 |
| 13 | 1，3，9 | 1 ~ 13 | 27 | 40 | 1，3，9，27 | 1 ~ 40 |
| 40 | 1，3，9，27 | 1 ~ 40 | 81 | 121 | 1，3，9，27，81 | 1 ~ 121 |
- 砝码按3的倍数增长；
- 每加一个砝码，称重范围增长到R'=3R+1
参考代码：
n=int(input())
sum=1
a=1
while a相关内容
热门资讯
修复 爱普生 EPSON L4...
L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
【PdgCntEditor】解...
一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...
监控摄像头接入GB28181平...
流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
在Word、WPS中插入AxM...
引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
protocol buffer...
目录 目录 什么是protocol buffer 1.protobuf 1.1安装 1.2使用...
【前端】‘??‘与‘||‘有什...
0 问题 经常写const data = res.data.a ?? ''或者const d...
Windows10添加群晖磁盘...
在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
牛客计算器的改良（Python...
文章目录1.题目描述2.输入描述:3.输出描述:4.示例15.分析6.代码7.结语 链接...
正大杯｜市调大赛｜2023备赛...
关键信息 同时随着精细化养宠趋势的深入，宠物消费类目日渐丰富。 本报告通过 Niuco...
QGIS下载在线地图（Goog...
前言 国内外有很多在线地图下载软件，但功能单一，基本上只能下载数据&#x...