每日练习之数学——砝码和天平

简介: 每日练习之数学——砝码和天平

砝码和天平

题目描述

运行代码

#include<iostream>
using namespace std;
int main()
{
  int w,m,T;
   cin>>T;
    while(T--)
    {
       cin>>w>>m;
        while(m)
        {
            if((m-1)%w==0)m=(m-1)/w;
            else if((m+1)%w==0)m=(m+1)/w;
            else if(m%w==0)m/=w;
            else break;
        }
        if(!m)
            cout<<"YES"<<endl;
        else 
            cout<<"NO"<<endl;
    }
}

代码思路

通过模拟天平的称量过程来检查是否能够使用给定的砝码(其质量为w的幂次)来表示一个特定的质量m。不是直接根据题目的数学思路来解决问题的,它实际上是在尝试模拟一个通过增加或减少少量质量来尝试使质量m能被w整除的过程。

  1. 首先读取测试数据的组数T。
  2. 对于每一组数据,读取w和m的值。
  3. 使用一个while循环尝试将m“调整”到一个可以被w整除的值。这里尝试了三种操作:
  • 如果m-1可以被w整除,则将m设置为(m-1)/w
  • 如果m+1可以被w整除,则将m设置为(m+1)/w
  • 如果m本身可以被w整除,则将m除以w。
  1. 如果在循环结束后m变为0,那么输出"YES",表示可以通过这些砝码来表示质量m(尽管这不是直接通过砝码组合,而是通过上述的“调整”过程)。
  2. 如果循环结束后m不为0,那么输出"NO",表示无法通过这些砝码来表示质量m。

改进思路

问题
  • 它没有直接利用到砝码是w的幂次这一特性。实际上,我们可以直接使用二进制表示法来判断m是否可以通过这些砝码来表示,而不需要这种“调整”过程。
  • 它假设了通过增加或减少1个单位的质量可以使得m变得可以被w整除,这在实际情况下并不总是正确的。
  • 即便m在某个点变得可以被w整除,这并不意味着它可以通过砝码组合来表示。因为代码没有检查这个整除后的m是否仍然在1到w的n次方减1的范围内。
改进

判断质量m是否可以用w的幂次砝码来表示,即判断m是否小于w(n+1)次方(其中n是砝码的最大幂次,但在这个问题中我们不需要确切知道n,只需要知道w(n+1)次方大于m即可)。

由于w可能非常大,直接计算w(n+1)次方可能会导致整数溢出。但幸运的是,我们只需要检查m是否小于w的平方,因为任何大于wm都可以通过w的更高次幂来表示(假设有足够的砝码)。

要判断一个质量m是否能用w的幂次砝码来表示,我们需要确保m可以表示为w的幂次的和,这相当于检查m的二进制表示是否只包含1(即mw的幂次的组合)。但是,由于我们不知道具体的n(砝码的最大幂次),我们可以简单地检查m是否小于或等于w的某个足够大的幂次,比如w的32次方(因为int类型通常有32位)。

然而,更简单的方法是检查m是否小于w(n+1)次方,其中n是使得w^(n+1)大于m的最小整数。由于w非常大,我们不能直接计算w^(n+1),但我们可以知道,如果m小于w的平方,那么它肯定可以用w的幂次来表示(因为w^0w^n的砝码可以覆盖从1到w^(n+1) - 1的所有整数)。

这个题目目前还没想到切实可行通过全部示例数据的数学方法解答的代码

目录
相关文章
|
10月前
|
算法 测试技术 C++
【数学归纳法 组合数学】容斥原理
【数学归纳法 组合数学】容斥原理
|
10月前
|
算法 测试技术 C#
【数学归纳法 反证法】菲蜀定理
【数学归纳法 反证法】菲蜀定理
|
机器学习/深度学习 算法
算法提高:组合数学| 卡特兰数的实现
卡特兰数列是组合数学中在各种计数问题中常出现的数列,其前几项为1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012…… 卡特兰数首先是由欧拉在计算对凸n边形的不同的对角三角形剖分的个数问题时得到的,即在一个凸n边形中,通过不相交于n边形内部的对角线,把n边形拆分成若干三角形,不同的拆分数用Hn表示,Hn即卡特兰数。
165 0
算法提高:组合数学| 卡特兰数的实现
|
算法 C++
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
蓝桥杯(聪明的猴子)克鲁斯卡尔算法最小生成树
127 0
(数论)蓝桥杯AcWing 1205. 买不到的数目
(数论)蓝桥杯AcWing 1205. 买不到的数目
65 0
|
算法
数学知识:中国剩余定理
复习acwing算法基础课的内容,本篇为讲解数学知识:中国剩余定理,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
233 0
数学知识:中国剩余定理
|
算法
【算法合集】关于数论
裴蜀定理:若 a, b是整数,且 (a, b) = d,那么对于任意的整数 x, y, ax + by 都一定是 d的倍数,特别地,一定存在整数 x, y使 ax + by = d成立。
116 0
【算法合集】关于数论
|
机器学习/深度学习 人工智能 Java
2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】
度度熊保护村庄 Accepts: 13 Submissions: 488 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 哗啦啦村袭击了喵哈哈村! 度度熊为了拯救喵哈哈村,带着自己的伙伴去救援喵哈哈村去了!度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地,牢牢的守住了喵哈哈村。
1650 0
[家里蹲大学数学杂志]第427期与反对称矩阵有关的一个行列式
设 $A$ 是 $n$ 阶实反对称矩阵, $D$ 是对角元均大于零的实对角矩阵. 试证: $|D+A|>0$.   证明: (1). 实反对称矩阵 $A$ 的特征值为纯虚数或零: $$\beex \bea &\quad A\al=\lm\al\quad(\al\neq 0)\\ &\ra A...
640 0