[POJ 3134] Power Calculus【IDDFS】

  • 2018-01-02
  • 0
  • 0

Problem:

Time Limit: 5000MS Memory Limit: 65536K

Description

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

x2 = x × xx3 = x2 × xx4 = 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 × xx3 = x2 × xx6 = x3 × x3x7 = x6 × xx14 = x7 × x7x15 = x14 × xx30 = x15 × x15x31 = 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 × x2x8 = x4 × x4x10 = x8 × x2x20 = x10 × x10x30 = x20 × x10x31 = 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 × xx4 = x2 × x2x8 = x4 × x4x16 = x8 × x8x32 = x16 × x16x31 = 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 nn 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

Source

Japan 2006

Solution:

DFS 能方便地记录路径,且节省空间,而 BFS 能高效地求出最小步数

迭代加深搜索(Iterative Deepening Depth-First Search, IDDFS)结合了两者的优点,且运算次数不会超过 BFS 的 2 倍

一个有效的可行性剪枝是若在最大指数 maxp 倍乘(即右移 <<)剩余次数 maxdep - dep 的基础上加上当前搜索到的次数 cur 仍然不能到达 n,则直接返回失败。与此对称的剪枝也同理可得。详见 Code #1Line 16, 17

Code #1 已经能通过 POJ 上的所有数据,但效率并不可观。

经过分析,可以得到另一个可行性剪枝。即将 vis[] 改为记录最小步数,若之前的尝试失败,且当前得到同一指数需要的步骤更多,则当前的尝试必定失败,因为之前的尝试中一定达到过当前的状态。所以若当前步数已经大于(不能等于)vis[] 中记录的值,则直接返回失败。此时 vis[] 必须在每次迭代前清空。详见 Code #2

Code #2 相比于 Code #1 效率有较大提升。

Code #1: O(玄学) [168K, 3813MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, maxdep;
int p[20], topp;
bool vis[2005], flag;

inline bool IDDFS(int cur, int dep, int maxp){
	if(cur == n) return 1;
	if(dep >= maxdep) return 0;
	if(cur + (maxp << maxdep - dep) < n) return 0;
	if(cur - (maxp << maxdep - dep) > n) return 0;  // Feasibility pruning
	for(register int i = 1; i <= topp; i++){
		if(cur + p[i] < 2000 && !vis[cur + p[i]]){
			vis[cur + p[i]] = 1, p[++topp] = cur + p[i];
			flag = IDDFS(cur + p[i], dep + 1, max(maxp, p[topp]));
			vis[cur + p[i]] = 0, topp--;
			if(flag) return 1;
		}
		if(cur > p[i] && !vis[cur - p[i]]){
			vis[cur - p[i]] = 1, p[++topp] = cur - p[i];
			flag = IDDFS(cur - p[i], dep + 1, max(maxp, p[topp]));
			vis[cur - p[i]] = 0, topp--;
			if(flag) return 1;
		}
	}
	return 0;
}

int main(){
	while(scanf("%d", &n) != EOF && n){
		for(maxdep = 0;; maxdep++){
			p[topp = 1] = 1;
			vis[1] = 1;
			if(IDDFS(1, 0, 1)){
				printf("%d\n", maxdep);
				break;
			}
		}
	}
	return 0;
}

Code #2: O(玄学) [172K, 875MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int n, maxdep;
int p[20], topp, vis[2005];
bool flag;

inline bool IDDFS(int cur, int dep, int maxp){
	if(cur == n) return 1;
	if(dep >= maxdep) return 0;
	if(cur + (maxp << maxdep - dep) < n) return 0;
	if(cur - (maxp << maxdep - dep) > n) return 0;  // Feasibility pruning
	for(register int i = 1; i <= topp; i++){
		if(cur + p[i] < 2000 && dep <= vis[cur + p[i]]){
			vis[cur + p[i]] = dep, p[++topp] = cur + p[i];
			flag = IDDFS(cur + p[i], dep + 1, max(maxp, p[topp]));
			topp--;
			if(flag) return 1;
		}
		if(cur > p[i] && dep <= vis[cur - p[i]]){
			vis[cur - p[i]] = dep, p[++topp] = cur - p[i];
			flag = IDDFS(cur - p[i], dep + 1, max(maxp, p[topp]));
			topp--;
			if(flag) return 1;
		}
		// Feasibility pruning: not to backdate, but to record the minimum steps
		/*
			Reason:
				The attempt of former calculating failed,
				and this time we get the same condition again taking more steps.
				What's worse is that those extra intermediate steps can't lead to the answer in another way
				because of the characteristic of IDDFS which is going further step by step.
		*/
	}
	return 0;
}

int main(){
	while(scanf("%d", &n) != EOF && n){
		for(maxdep = 0;; maxdep++){
			p[topp = 1] = 1;
			memset(vis, 0x3f, sizeof(vis)), vis[1] = 0;
			if(IDDFS(1, 0, 1)){
				printf("%d\n", maxdep);
				break;
			}
		}
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai