请教一个算法问题

cokeboL

回复 8# windoze


    我说的root是第0层，3^0是1不。。

cokeboL

1. int getParentIdx(int idx)
   
2. {
   
3.         if (idx == 0)
   
4.         {
   
5.                 return 0;
   
6.         }
   
7.         int floor = 0;
   
8.         int total = 0;
   
9.         int start = 0;
   
10.         int end = 0;
    
11.         int parentStart = 0;
    
12.         int parentEnd = 0;
    
13.         int sub = 0;
    
14.         int parent = 0;
    
15. 
    
16.         while (true)
    
17.         {
    
18.                 total = pow(3.0, floor);
    
19.                 if (floor == 0)
    
20.                 {
    
21.                         parentStart = parentEnd = 0;
    
22.                 }
    
23.                 else
    
24.                 {
    
25.                         start = end + 1;
    
26.                         end = end + total;
    
27.                         if (idx >= start && idx <= end)
    
28.                         {
    
29.                                 sub = idx - start;
    
30.                                 parent = parentEnd - sub / 3;
    
31.                                 return parent;
    
32.                         }
    
33.                 }
    
34.                 parentStart = start;
    
35.                 parentEnd = end;
    
36. 
    
37.                 floor++;
    
38.         }
    
39. }
    
40. 
    
41. void testCTTree()
    
42. {
    
43.         printf("2  -> parent: %d\n", getParentIdx(2));
    
44.         printf("3  -> parent: %d\n", getParentIdx(3));
    
45.         printf("5  -> parent: %d\n", getParentIdx(5));
    
46.         printf("7  -> parent: %d\n", getParentIdx(7));
    
47.         printf("11  -> parent: %d\n", getParentIdx(11));
    
48.         printf("15  -> parent: %d\n", getParentIdx(15));
    
49.         printf("17 -> parent: %d\n", getParentIdx(17));
    
50. }
    

复制代码

输出：

1. 2  -> parent: 0
   
2. 3  -> parent: 0
   
3. 5  -> parent: 3
   
4. 7  -> parent: 2
   
5. 11  -> parent: 1
   
6. 15  -> parent: 12
   
7. 17 -> parent: 11

复制代码

然后套到我之前给的那个循环里就ok了

cokeboL

1. int getParentIdx(int idx)
   
2. {
   
3.         if (idx == 0)
   
4.         {
   
5.                 return 0;
   
6.         }
   
7.         int floor = 0;
   
8.         int total = 0;
   
9.         int start = 0;
   
10.         int end = 0;
    
11.         int parentStart = 0;
    
12.         int parentEnd = 0;
    
13.         int sub = 0;
    
14.         int parent = 0;
    
15. 
    
16.         while (true)
    
17.         {
    
18.                 total = pow(3.0, floor);
    
19.                 if (floor == 0)
    
20.                 {
    
21.                         parentStart = parentEnd = 0;
    
22.                 }
    
23.                 else
    
24.                 {
    
25.                         start = end + 1;
    
26.                         end = end + total;
    
27.                         if (idx >= start && idx <= end)
    
28.                         {
    
29.                                 sub = idx - start;
    
30.                                 parent = parentEnd - sub / 3;
    
31.                                 return parent;
    
32.                         }
    
33.                 }
    
34.                 parentStart = start;
    
35.                 parentEnd = end;
    
36. 
    
37.                 floor++;
    
38.         }
    
39. }
    
40. 
    
41. void testCTTree()
    
42. {
    
43.         printf("2  -> parent: %d\n", getParentIdx(2));
    
44.         printf("3  -> parent: %d\n", getParentIdx(3));
    
45.         printf("5  -> parent: %d\n", getParentIdx(5));
    
46.         printf("7  -> parent: %d\n", getParentIdx(7));
    
47.         printf("11  -> parent: %d\n", getParentIdx(11));
    
48.         printf("15  -> parent: %d\n", getParentIdx(15));
    
49.         printf("17 -> parent: %d\n", getParentIdx(17));
    
50. }
    

复制代码

输出：

1. 2  -> parent: 0
   
2. 3  -> parent: 0
   
3. 5  -> parent: 3
   
4. 7  -> parent: 2
   
5. 11  -> parent: 1
   
6. 15  -> parent: 12
   
7. 17 -> parent: 11

复制代码

然后套到我之前给的那个循环里就ok了

cokeboL

考虑运行效率，初始化的时候生成个数组吧，数组元素保存每层的起点idx和终点idx，然后getParentIdx的时候查表再加个二分，要省些

VIP_fuck

回复 13# cokeboL


    能把你的公式写一下吗，判断某一个节点的子节点是哪个，


   正在看代码，，，

VIP_fuck

回复 14# cokeboL


    服。

    用数据测试，正确。

    我的思路比较死，是考虑每个节点的子节点怎么计算，而且，只考虑加，乘，除，唯独没有考虑减法。

Kurosaki_Ichigo

很规律的排列，献丑了。

1. #include <stdio.h>
   
2. 
   
3. void getAncestors(int * ancestor, int layer)
   
4. {
   
5.         static int from, to;
   
6.        
   
7.         if(*ancestor == 0){ from = to = 0; return;}
   
8.         ancestor[1] = (ancestor[0] - 1) / 3;
   
9.         getAncestors(ancestor + 1, !layer);
   
10.         from = from * 3 + 1;
    
11.         to = (to + 1) * 3;
    
12.         if(layer) *ancestor = from + to - *ancestor;
    
13. }
    
14. 
    
15. int commonAncestor(int a, int b)
    
16. {
    
17.         int La[24] = {a}, Lb[24] = {b}, *pa, *pb;
    
18.        
    
19.         getAncestors(La, 0);
    
20.         getAncestors(Lb, 0);
    
21.         for(pa = La, pb = Lb; *pa != *pb; *pa > *pb ? pa++ : pb++);
    
22.         return *pa;
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.         int a, b;
    
28.        
    
29.         scanf("%d %d", &a, &b);
    
30.         printf("%d\n", commonAncestor(a, b));
    
31.         return 0;
    
32. }

复制代码

VIP_fuck

回复 17# Kurosaki_Ichigo


   

论坛牛人够多

我自己只是无限接近这个结果，但是始终都差那么一点，惭愧。

cokeboL

真要实现的话，这种树用数组存储比较好，idx就是child下标，生成的时候父子关系就确定

folklore

这个不是满三叉树么， 用数学公式能算出来啊。