| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1944 人关注过本帖
标题:最小乘法次数的问题
只看楼主 加入收藏
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
结帖率:95.37%
收藏
已结贴  问题点数:20 回复次数:9 
最小乘法次数的问题
给你一个非零整数,让你求这个数的n次方,每次相乘的结果可以在后面使用,求至少需要多少次乘。
如24:2*2=22(第一次乘),22*22=24(第二次乘),所以最少共2次。
211:2*2=22(第一次乘),22*22=24(第二次乘)24*24=28(第三次乘)28*22=210(第四次乘)210*21=211(第五次乘)所以最少共5次。
输入
第一行m表示有m(1<=m<=100)组测试数据;
每一组测试数据有一整数n(0<n<=10000);
输出
输出每组测试数据所需次数s;
样例输入
3
2
3
4
样例输出
1
2
2

该怎么写?
下面是从网上搜的答案。

#include <stdio.h>  
  
int main()  
{  
    int n,count,m;   
    scanf("%d",&m);  
    while(m--)  
    {  
        scanf("%d",&n);  
        count=0;  
        while(n!=1)  
        {  
            if(n&1)
                count++;  
            count++;  
            n>>=1;  
///这一块没看懂是怎么回事。
        }  
        printf("%d\n",count);  
    }  
    return 0;  
}
搜索更多相关主题的帖子: 最小 次数 测试 输出 count 
2017-12-02 22:12
Alien_Lee
Rank: 8Rank: 8
来 自:Linux帝国
等 级:蝙蝠侠
威 望:7
帖 子:149
专家分:739
注 册:2016-7-19
收藏
得分:4 
不知所云!

  DEBUG的过程就是进步的过程,每一个小错误都是大问题!...
2017-12-04 19:15
liaohs
Rank: 4
等 级:业余侠客
威 望:7
帖 子:61
专家分:292
注 册:2017-11-26
收藏
得分:4 
题目叙述看不懂。

红字部分的意思是:
假设n的二进制表示有k位(长度), 其中有m个1,
结果count是k+m-2
2017-12-04 20:36
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:4 
如2^4:2*2=2^2(第一次乘),2^2*2^2=2^4(第二次乘),所以最少共2次。
2^11:2*2=2^2(第一次乘),2^2*2^2=2^4(第二次乘)2^4*2^4=2^8(第三次乘)2^8*2^2=210(第四次乘)2^10*2^1=2^11(第五次乘)所以最少共5次。
---------------- 以上是我帮你修改的题目说明 ----------------

以2^11为例,11 = 8+2+1
2^8 = 2^2^2^2 即需要乘3次,同时也有了 2^1、2^2,所以共需5次
总结一下,对于2^n,将n化成二进制,先看最高位的1,在什么位上就需要几次。然后看其它位,有1的位就需要1次。
2017-12-05 10:12
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:0 
回复 4楼 rjsp
你是怎样想到把N转换为二进制来算的呢?
            if(n&1)
                count++;  
            count++;  
            n>>=1;
还有一个问题:
我这一块代码是哪一行是计算最高位1转换的次数的?
2017-12-05 11:23
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:0 
回复 3楼 liaohs
不是很理解。。
2017-12-05 11:23
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:0 
回复 2楼 Alien_Lee
2017-12-05 11:24
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:4 
回复 5楼 花脸
以下是引用花脸在2017-12-5 11:23:22的发言:

你是怎样想到把N转换为二进制来算的呢?
            if(n&1)
                count++;  
            count++;  
            n>>=1;
还有一个问题:
我这一块代码是哪一行是计算最高位1转换的次数的?



4楼解释已经很明白~
结合4楼解释这行代码一目了然~
count++已经在转换二进制的过程中累加最高位1转换的次数了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-05 11:36
花脸
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:9
帖 子:788
专家分:907
注 册:2017-1-4
收藏
得分:0 
回复 8楼 九转星河
恩好的、
2017-12-05 11:47
Jonny0201
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:贵宾
威 望:52
帖 子:488
专家分:2603
注 册:2016-11-7
收藏
得分:4 
3 为什么会输出 2
3 = 3 ^ 1
一次就能得到,不应该是 1 吗?
2017-12-06 01:06
快速回复:最小乘法次数的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.038080 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved