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相关内容
热门资讯
监控摄像头接入GB28181平...
流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘...
在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer...
目录 目录 什么是protocol buffer 1.protobuf 1.1安装 1.2使用...
Fluent中创建监测点
1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据...
MySQL下载和安装（Wind...
前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
MFC文件操作
MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...
在Word、WPS中插入AxM...
引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
有效的括号
一、题目 给定一个只包括 '('，')'，'{'，'}'...
【Ctfer训练计划】——(三...
作者名：Demo不是emo 主页面链接：主页传送门 创作初心ÿ...