两个算法问题！(100分)

（1）Hanoi塔问题有非递归算法吗？有的话，怎么实现？ 给出程序！
（2）求解X立方（或者X平方）的值，要求只用加法。 给出原理和程序！

1，应该没有吧。为什么要用非递归呢？
2，用加法？如果X是整数还好办，否则...
有必要这样做吗？

X平方
1^=1
2^=1+3
3^=1+3+5
看明白了吗?

dhl2001,你的算法不通用。如果是3次方，。。。n次方呢？
志强：我建议第一个问题，你直接问那个PhD。
//---------------------------------------
functiondo
it(DS,ZS:integer):integer;
var
x,i,j:integer;
begin
x:=0;
if ZS=2 then
begin
for i := 0 to DS-1do
x:=x+DS;
end
else
begin
for i :=0 to DS-1do
x:=x+doit(DS,ZS-1);
end;
result:=x;
end;
//-----------------------------------------

hanoi有非递归解法:
1.将最小的盘子移到右侧的柱子上.(如果最小的盘子在最右侧的柱子上,则移到最左的柱子上)
2.做一次不涉及最小盘子的合法移动
3.判断是达到目标,是退出,否转1.
n很大时用递归会内存溢出,这中算法则不会.

难道不知道所有的递归程序实际上都是可以转化为非递归的吗？
用栈就可以实现了，找一本正点的数据结构书，肯定会有提到。
至于平方、N次方，如果是整数，楼上savenight兄的算法算是很cool的了，如果是浮点偶就无能为力了；）

>>难道不知道所有的递归程序实际上都是可以转化为非递归的吗
这种也算答案吗？？？
关于X^n
我想用导数的概念很容易改为多个循环的累加的

用数组模拟栈

大学课本数据结构书上有写将递归算法转换成非递归算法的算法

同意zoufeiyy和yxyyyy，用栈可以实现递归，很多数据结构的教材都有

都是废话！

(转载)
发信人: mmc (毛毛虫-吃青菜), 信区: Datastructure
标 题: 汉诺塔非递归算法(转载)
发信站: 出水芙蓉 (2002年01月02日18:56:56 星期三), 站内信件
/* 这个算法是用java做的.
读完后就知道,汉诺塔问题其实就是一颗满二叉数
1 h(n,a,b,c)= h(n-1,a,c,b) + a->c + h(n-1,b,a,c) 对应一个二叉树
（a,b,c) ---0层
/ /
(a,c,b) (b,a,c) ---- 1层
2 实际上，整个递归算法走完了一个 n-1 层的二叉树，***是满二叉树。该树中，每
个节点的
左孩子等于该节点第二、三个参数交换，右孩子等于该节点第一、二个参数交换
3 我们完全可以通过建立二叉树的方法来实现该问题（第0层节点三个参数为 a,b,c),对
该树进行中序（中根）
遍历，便得到了整个操作序列。（各节点的处理为输出 第一参数 -> 第三参数）
4 完全二叉树可以用数组来表示和实现。但是，为了方便，我们要按照 中序（中根）
来建树。各节点间关系如下：
（为了方便，我们将第一个元素序号设为1，最上层为第 0 层，n 个盘子，设立一个
n-1层的树）
第 i 层第一个元素序号 为 2^( n-1-i)
第 i 层两个相临元素序号差值 2^( n-i) (当 i!= 0时）
-----上述关系无须证明，只把各节点序号用二进制数表示，则一目了然。
********************************************************************
本算法缺点：空间复杂度为 2^ n .但在此基础上，可以引入堆栈，减少空间需求。
但这样会减弱代码的可读性。
//*********************************************************************
5 以下讨论与本算法无关，但是可以让我们更进一步认识到该问题的实质
给树的每个边附加一个数 ：左向边为0 ，右向边为 1
给每个节点标记为从根节点到该节点的路径中全部边。如图
@
/ /
0 / / 1
/ /
节点标记为“0” @ 略
/ /
0 / / 1
/ /
略 @ 节点标记为 “01”
| 1 0 0 |
定义 T(0)=| 0 0 1 |
| 0 1 0 |
| 0 1 0 |
定义 T(1)=| 1 0 0 |
| 0 0 1 |
两个矩阵，则
(a,b,c) * T(0)=( a,c,b )
(a,b,c) * T(1)=( b,a,c )
因此 节点 P的左孩子参数 = p 的参数 * T(0)
节点 P的右孩子参数 = p 的参数 * T(1)
各节点的 参数等于（a ,b,c) * 标记序列对应的 矩阵序列。
如上图最下层节点三个参数
= 最上层节点三个参数 * T(0) * T(1)
这样，每个节点的意义和节点间的关系都非常清楚
*/
class H{
char [][] oper;
H(int n){
int total=pow;
oper=new char[total][3];//用于前序存放n-1层满二叉树,oper[0]冗余不用
int first=total/2;//first 指向每层第一个元素，当前为第0层第一元素
oper[first][0] ='a';//对第0层赋值
oper[first][1] ='b';
oper[first][2] ='c';
//从第0层开始,到第n-2层，每层对下一层赋值
for(int i=0;i<n-1;i++){
int gap=2*first;//第i层同层元素的间隔(i!=0时)
int subfirst=first/2;//下一层第一个元素
int subgap=gap/2;
for(int j=first;j<total;j+=gap){//第i 层每个元素，对其下层
oper[subfirst][0] =oper[j][0] ;
oper[subfirst][1]=oper[j][2];
oper[subfirst][2]=oper[j][1];
subfirst+=subgap;
oper[subfirst][0] =oper[j][1];
oper[subfirst][1]=oper[j][0] ;
oper[subfirst][2]=oper[j][2];
subfirst+=subgap;
}
first/=2;//first
}
System.out.println( "按照二叉数的格式化输出<左边为根，
向上为左子树，向下为右子树>");
for(int k=1;k<total;k++){
int tem=k,lay=n-1;
while (tem%2==0){tem/=2;lay--;}
tem=lay;
while (lay>0){System.out.print(" ");lay--;}
System.out.print (""+oper[k][0]+">"+oper[k][1]+">>"+oper[k][2]);
while(tem<n-1){System.out.print("----------");tem++;}
System.out.println (" (the "+k+ " th step)");
}
System.out.println( "/n按照二叉数中序便利输出（注意各行的对应关系）/
n");
for(int k=1;k<total;k++)System.out.println (""+oper[k][0]+">"
+oper[k][1]+">>"+oper[k][2]);
}
int pow(int y){
int result=1;
while(y>0){
result*=2;
y--;
}
return result;
}
}
public class Class1
{
public static void main (String[] args)
{
H h=new H(3);
try{System.in.read ();}catch (Exception e){}
}
}

你小子该给分了吧？ 对了，你的ftp可以关了.

>>都是废话！
经典
>>同意zoufeiyy和yxyyyy，用栈可以实现递归，很多数据结构的教材都有
递归本来就是用栈实现的
所谓用栈来实现递归，有意义吗
要的是非递归算法！！！

吃饱没事做！

我希望你买一本delphi基本算法的书，25元，书名不记得了

向高手们们致敬！！[]

乘法转化为加法，就是先建立一个一位数乘法的表格（相当于九九表），然后模拟手工计算乘法的过程就行了

1. 任何递归算法都有非递归算法对应，
递归算法是模拟人的思维，让计算机去做事情，
非递归是模拟计算机的思维，后者要加堆栈或队列实现，
理论的证明是有的， 有兴趣的可以去研究一下图灵机和自动机。
2. X平方
X(1)=1
X(2)=1+3
X(3)=1+3+5
X(4)=1+3+5+7
3. X立方
我想先可以转换成平方吧，
X(1)=1
X(2)=4+4
X(3)=9+9+9
X(4)=16+16+16+16
用个两层的循环就搞定了， Easy 啊

s := 0;
for i := 1 to ndo
begin
t := 0;
for j := 1 to ndo

begin
t := t + j;
end;
s := s + t;
end;

这个算法肯定不是最优的， 应该还有别的好方法， 随便想着玩的，

>>理论的证明是有的， 有兴趣的可以去研究一下图灵机和自动机。
请教哪里有
自动机学过，在编译中
但语法分析是词法分析程序不能完成的
而且语法分析中不用递归就要用栈的
用栈消除递归是没有意义的（就不是消除递归）
x的n次方，上面我写了
用数学方法，求导数，是可以解决的
X^3 ------> 3*X^2
X^2 ------> 2*X
求导数一次，加一个循环而已