迭代加深搜索——POJ 3134

2024-09-05 04:32
文章标签 搜索 poj 迭代 加深 3134

本文主要是介绍迭代加深搜索——POJ 3134,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对应POJ题目: 点击打开链接


Power Calculus
Crawling in process... Crawling failed Time Limit:5000MS    Memory Limit:65536KB    64bit IO Format:%I64d & %I64u
Submit Status

Description

Starting with x and repeatedly multiplying by x, we can computex31 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 computex31 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 computex31 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 computexn by multiplication and division starting withx for the given positive integern. Products and quotients appearing in the sequence should bex 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 computexn starting withx 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
 
 
    
不断加大搜索的深度 每层搜索就用前一步得出的值和之前产生的所有值进行乘或除运算得出新的值
剪枝 : 假设当前已经算出来的x的幂的次方数最大是 n_max 那么如果还可以深入搜索 3 层的话 x 的次方数最多只可能变成 n_max << 3 
所以如果 n_max << (还剩下的搜索层数) < n 的话已经没有继续搜索的必要 回退
 #include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=1000+10;
const int INF=1<<30;
using namespace std;
int n,ans=INF;
int a[MAXN];
int maxh;bool dfs(int x, int cur)
{if((x*(1<<(maxh-cur)))<n) return false;if(cur>maxh) return false;a[cur]=x;if(x==n){return true;}int t=cur;for(int i=0; i<=t; i++){if(dfs(x+a[i], cur+1)) return true;if(x-a[i]>0){ if(dfs(x-a[i],cur+1)) return true;}else if(dfs(a[i]-x,cur+1)) return true;}return false;
}int main()
{//freopen("in.txt","r",stdin);while(scanf("%d", &n), n){maxh=0;memset(a,0,sizeof(a));while(dfs(1,0)==false){ans=INF;memset(a,0,sizeof(a));maxh++;}printf("%d\n", maxh);}return 0;
}


这篇关于迭代加深搜索——POJ 3134的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1137953

相关文章

Mybatis从3.4.0版本到3.5.7版本的迭代方法实现

《Mybatis从3.4.0版本到3.5.7版本的迭代方法实现》本文主要介绍了Mybatis从3.4.0版本到3.5.7版本的迭代方法实现,包括主要的功能增强、不兼容的更改和修复的错误,具有一定的参考... 目录一、3.4.01、主要的功能增强2、selectCursor example3、不兼容的更改二、

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int