2 shunfurh shunfurh 于 2017.08.31 00:29 提问

Power Calculus

Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:

x2 = x �� x, x3 = x2 �� x, x4 = x3 �� x, ��, x31 = x30 �� x.

The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:

x2 = x �� x, x3 = x2 �� x, x6 = x3 �� x3, x7 = x6 �� x, x14 = x7 �� x7, x15 = x14 �� x, x30 = x15 �� x15, x31 = x30 �� x.

This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:

x2 = x �� x, x4 = x2 �� x2, x8 = x4 �� x4, x8 = x4 �� x4, x10 = x8 �� x2, x20 = x10 �� x10, x30 = x20 �� x10, x31 = x30 �� x.

If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):

x2 = x �� x, x4 = x2 �� x2, x8 = x4 �� x4, x16 = x8 �� x8, x32 = x16 �� x16, x31 = x32 �� x.

This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.

Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n. Products and quotients appearing in the sequence should be x to a positive integer��s power. In others words, x−3, for example, should never appear.

Input

The input is a sequence of one or more lines each containing a single integer n. n is positive and less than or equal to 1000. The end of the input is indicated by a zero.

Output

Your program should print the least total number of multiplications and divisions required to compute xn starting with x for the integer n. The numbers should be written each in a separate line without any superfluous characters such as leading or trailing spaces.

Sample Input

1
31
70
91
473
512
811
953
0
Sample Output

0
6
8
9
11
9
13
12

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.15 00:19
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
poj 3134 Power Calculus (IDA*)
题意:求由X得到X^n的最少步数。 分析:迭代加深搜索。 剪枝:1、如果大于当前限制的深度,停止搜索。             2、如果当前的数通过自身相乘(即指数相加 最快方式)都不能达到n,停止搜索。 感想: 写到后来越来越像什么用dfs搜索某个集合的幂集中有多少元素,取和不取某个数,然后继续搜。。 真的很像啊。。。虽然我每次都写不好DFS。。。 #inc
UVA - 1374 Power Calculus 迭代深搜
题目大意:问从1变到n至少需要多少步。变换规则如下 1.变化过程中的中间结果可以任意使用 2.每次只能挑选两个数进行加减解题思路:先算一下至少需要多少步,然后在如果在当前步数下无法到达结果的话,就当前步数加1,继续搜索下去#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn
Power Calculus
题意: 给出次数n,求至少要乘除几次可达到n次 思路: 首先初始化出最少步数,即累乘得到一个>=n的次数(如果为n那么就是结果,如果>n那么至少还需要除操作) 然后用一个数组存储已经得到的次方数用于使用,同时操作乘与除,用dfs考虑所有的情况,直到base足够大,能得到cur==n 代码: #include #include #include #include using name
poj 3134 Power Calculus iddfs(迭代深搜)
iddfs入门题。 //poj 3134 //sep9 #include using namespace std; int n,deep; int a[30]; bool iddfs(int pos) { int t; if(pos>deep) return false; if(a[pos]<<(deep-pos)<n) return false; if(a[pos]==n) ret
POJ 3134 Power Calculus (IDA*)
题目类型  搜索题(IDA*) 题目意思 给你一个p*q的国际象棋棋盘 输出一个字典序最小的方案 (行编号为字母 列编号为数字 字母+数字等于一个棋子的位置)  | 其中 1 这个方案要求 马从起点跳到终点中间经过棋盘所有的点且不重复(起点终点可以自己选定) 解题方法 参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
UVALive - 3621 Power Calculus
题意:给出x和正整数n,问最少需要几次乘除法可以得到x^n 思路:迭代搜索+减枝 #include #include #include #include using namespace std; const int MAXN = 1010; const int INF = 10000007; int arr[MAXN],num; int dfs(int n,int step){
UVA - 1374 Power Calculus
题目大意:给出 n,问说至少计算几步得到 x^n。解题思路:迭代深搜,枚举步数,然后深搜判断是否可行。需要优化,当当前数s按照最大方案执行后仍然小于n,则说明不可行。#include <cstdio> int n, MAX, A[35];bool DFS(int cur, int now){ if (cur > MAX || now <= 0 || now << (MAX - cur) <
[codevs 1288] 埃及分数 [IDdfs 迭代加深搜索 ]
题目描述 Description 在古埃及,人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。 如:2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。 对于一个分数a/b,表示方法有很多种,但是哪种最好呢? 首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越 好。 如: 19/45=1/3 + 1/12 + 1/180 19/45=1/
James Stewart Calculus, 6th edition 英文高清彩页版.pdf
James Stewart Calculus, 6th edition 英文高清彩页版.pdf 北美最流行的微积分教材,第六版
Thomas' Calculus 13th Edition[pdf]
Thomas' Calculus 13th Edition English Edition with bookmarks