如果有空,请大家研究一个算法问题:整数变换.

题目:关于整数i的变换f和g定义如下:f(i)=3*i;g(i)=[2/i]([]表示下取整,相当于delphi中的floor),试设计一个算法,对于给定的两个整数n和m,用最少的f和g变换次数将n变换为m.例如,我们可以将整数15用4次变换为整数4: 4=gfgg(15). 当整数n不可能变换为整数m时,算法该如何处理?

我的理解,问题很明显可以用回溯法求解,它的状态树是一棵二叉树,但问题是怎么判断一个数不能变换为另一个数,否则状态树可能是无限深度的,无法停止.

41 个解决方案

#1

无需写代码,重在解决问题的思路.

#2

mark

#3

关注

#4

怎么现在大家对算法都这么没兴趣了?

#5

友情帮顶诶...

#6

不懂，f和g的定义都是不变的吗？这个g应该是[i/2]吧

友情帮顶诶...

#7

不懂，f和g的定义都是不变的吗？这个g应该是[i/2]吧

友情帮顶诶...
------->
就是嘛，害我疑惑了半天,以为自己理解出了问题.晕死

#8

,但问题是怎么判断一个数不能变换为另一个数,否则状态树可能是无限深度的,无法停止.

既能除2,又能乘3,
既能变大,又可以变小,唉,咋个判断到哪个数字就不可能转换呢?

#9

顶

#10

比较高深，学习

#11

应该是已经定义了的
不然就不会想算法去研究最少次数了

#12

友情UP

#13

4=g(f(g(g(15))))
[2/15]不就==0了？
0不能做除数，那不是出问题了么？？？

#14

g(i)=[i/2]
留名，思考中

#15

是我写错了,应该是g(i)=[i/2]

#16

没人有兴趣研究吗?

#17

想了很久,有一点进展:
从二进制数上考虑,g是向右移一位,f是左移一位在加上原数.如果一个数m的二进制经过任意次的上述两种运算,仍得不出另一个数n,就可以判断不能转换.
现在的问题转移到,一个数乘3,也就是左移一位在加上原数,变换之后,在二进制形式上有什么规律?
再研究研究

#18

学习中...

#19

想了一下，感觉上一般情况下用搜索做出解是很快的：

将规则反一下，不由n变为m，而由m变成n。则规则变为：i->i/3(i必须是3的倍数)或 i->i*2或i->i*2+1。

这样，对于一个区间[a,b]，它可以变为：[[(a+2)/3],[b/3]]+[a*2,b*2+1]。
根据这点，搜索的第一层就是[m,m]这个区间，以后的每一层是由上一层扩展出来的区间。由于这些区间有很多是可以合并的，所以第i层的区间个数不是2^(i-1)个，而是一个比较小的数，事实上，到达一定深度后，区间的个数会保持在一个常数，比如说当m=4时，这个常数只有5(也就是每一层至多有5个区间)。

同时，到达一定深度后，必会出现区间包含子区间[1,3](谁能帮忙证一下？)，这个区间由上面两条扩展，可扩展出[1,7],[1,15],[1,31]……，[1,2^p-1]，扩展到包含n这个数的区间只要log(2)n次，加上前面得到[1,3]这个区间的层数，总的搜索层数应该不会很大。

祝楼主好运。

#20

我的初步想法和回复人： jellypillar(新型人类) ( ) 信誉：100 有点相似，

如果反过来考虑，从4变换成15可能要容易一点 (m->n)，那么
f(x)变成          
f'(x)              x / 3                         (且3*f'(x) = x)
g(x)变成两个函数
  g1(x)           x * 2
  g2(x)           (x * 2) + 1

我有两种思路，
一种是直接搜索m到n的路径，搜索时我们只有当中间结果是3的倍数时才会考虑应用f'(x)，
这样就减少了很多搜索分枝了

另一种是先将m通过f'/g1/g2这些函数变成1，然后从1开始应用f/g两个函数变换成n，
如果成功，那么存在一条从m到n的路径，如果m->1 和 1->n两个过程中靠近1的地方
有相互抵销的部分可以消去，这样搜索不知道会不会快一点

另外我想，m能够通过f'/g1/g2变换成1，如果对于任意的n能够从1开始，应用f/g变换成n，
那么就必定存在一条从m到n的路径，
换句话说，如果能够证明，对于任意n > 0，通过应用f/g，
能够变换成n+1的话，就必定存在一条从m(>0)到n的路径，
也必定存在一条从n到m的路径

#21

顶一下^_^

#22

我猜想,所有的整数都可以进行转换.
1.首先,所有的整数都可以经过有限次的g变换转换为1.
2.然后,我考虑哪些数不能由1变出,但是经过试验,我找不出这样的数.
3.我编了一个程序,希望在计算机的帮助下找到一个不能由1变成的数,但是随着计算范围的扩大,由1不能变成的数也随之扩大.
结果如下:
运算范围     (最小的)由1不能变成的数
1000         161
10000        
100000
1000000
10000000
因此我猜想随之计算范围趋于无穷,这样的数也趋向于无穷大.因此所有的整数都可以通过1变化出来,所以任意整数之间也可以变换.
这只是我的一个猜想,如果能给一个严格的证明就好了.

#23

//这是我的测试程序,供参考
unit Main;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs,Contnrs, StdCtrls;

const
  N=10000000;
type
  TNum=class
    Value:integer;
  end;
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Button2: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Private declarations }
    Contained:Array [1..N] of boolean;
    que:TQueue;
    procedure AddNum(va:integer);
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
  que:=TQueue.Create;
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  que.Free;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  num:TNum;
  v,t1,t2,i:Integer;
begin
  num:=TNum.Create;
  num.Value:=1;
  que.Push(num);
  while (que.Count>0) do
  begin
    num:=TNum(que.Pop);
    v:=num.Value;
    num.Free;

    t2:=v div 2;
    if not Contained[t2] then
        AddNum(t2);
    t1:=v*3;
    if t1<=N then
      if not Contained[t1] then
        AddNum(t1);
  end;

  for i:=1 to N do
  if not Contained[i] then
  begin
    memo1.Lines.Add(inttostr(i));
    break;
  end;
end;

procedure TForm1.AddNum(va: integer);
var
  num:TNum;
begin
  num:=TNum.Create;
  num.Value:=va;
  que.Push(num);
  Contained[va]:=true;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  // memo1.Lines.Add(inttostr(2));
end;

end.

#24

关键是怎么证明，什么样才可计算，我也估计任意数之间能够互相变换，有证明吗？我连怎么证明都没有头绪

#25

你找到1不能变换到的数没用的，说不定这个数不用变到1就可以生成1所不能生成的数
整个难点就在于g运算的反函数无法确定啊

#26

如果1能变换为任意数 ,就可以推断出任意两个数之间都能变换,并不是为了找到最简单的变换方法,而是证明了可变换.

#27

运算范围     (最小的)由1不能变成的数  
1000         161
10000        728
100000       6560
1000000      59048
10000000     531440
算最后一个数用了1个多小时,在我的旧笔记本上(P3 1.1G)
程序可以改进一下,把 div 2 改成 shr 1; 把 *3改成 左移加原数;在队列中无需要存对象,只需要把Integer强转为Pointer存入,取出时再转为Integer

现在可以说小于531440的数都可以由1变换来,但531440需要多少次变换才能得出,还未知

这个算法太费时间,无法计算更大的范围,不过猜想应该是成立的

#28

我想问一下，你这个问题有没有什么实际应用，还是纯粹的数学问题？

#29

是理论问题,不是实际问题.

#30

好多星星啊

#31

数学问题？是数论问题

#32

是不是角古猜想？

#33

不要把简单问题复杂化,可以考虑m,n两数的商值,无非是3的X次方与1/2的Y次方的积如何与那个商值相等而又让X+Y最小的问题罢了!

#34

Cipherliu(孤鹰) 你想的和我一样,只不过,要给出最少的变换次数有点难啊.

#35

感谢大家的参与
现在可以暂不考虑次数最少的变换(实际上,我上面给的那个算法就可以算出次数最少的变换.在那个程序里我算的是把1变成其它数,如果把初值改为m,就可以算出,由m经过最少次数的变换可以变成那些数.)

如果定下一个n,想找到一条变换路径到m,最大的问题是计算机会不会陷入无限的搜索之中而无法结束,或者在整数类型溢出时还得不到结果.(当然可以自定义任意长的整形数结构来解决后一问题)

归要结底,就是我们需要做出判断,两个数是否可变换,如果可变换,就让机器辛苦一点求出它,如果不能变换,也不要让机器做无用的搜索而不能自拔.

就现在的现象看来,似乎所有的数都可变换,但怎么证明呢?这好象是数论领域的问题,超出了计算机科学研究的范围,但有兴趣有时间研究一下也无妨.

#36

没人关注了吗?

#37

留个脚印

#38

顶一下

#39

好像就是角古猜想哦~

一个可以实现,但是还不能证明的问题.

#40

顶一下

#41

顶一下