老大们，请教算法问题，很难

smartham_whl

[问题描述]
　　有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

　　例如 N=4，4 堆纸牌数分别为：
　　①　9　②　8　③　17　④　6
　　移动3次可达到目的：
　　从 ③ 取 4 张牌放到 ④ （9 8 13 10） ->; 从 ③ 取 3 张牌放到 ②（9 11 10 10）->; 从 ② 取 1 张牌放到①（10 10 10 10）。
[输 入]：
　　键盘输入文件名。文件格式：
　　N（N 堆纸牌，1 <= N <= 100）
　　A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
[输 出]：
　　输出至屏幕。格式为：
　　所有堆均达到相等时的最少移动次数。‘
[输入输出样例]
a.in：
　4
　9 8 17 6

屏慕显示：
　3
    

chenjn

1. 
   
2. 先计算总牌数total和平均数avg
   
3. 用move(n)递归从An->;A1判断:
   
4. An>;平均数，判断pai==0则把多余牌数移到A[n-1]，移动次数+1，调用move(n-1)
   
5.                pai>;0，比较多余牌数和pai，如果多余牌数<pai，则调用move(n-1)
   
6.                                        如果多余牌数>;=pai，则移动pai张牌到A[n+1]，移动次数+1，执行move(n+1)
   
7. 
   
8. An=平均数，则判断n=1则返回，否则执行move(n-1)
   
9. 
   
10. An<平均数则设一个变量pai保存离平均数所差的牌数，然后调用move(n-1)
    
11. 
    
12. 
    
13. 
    
14. 不知道这个算法怎么样呀，写得有点乱，排版不好排

复制代码

hannibal

算法是写得出，可是怎么保证是最少解呢。。？

chenjn

我觉得只要在A1-An任何一个地方和相邻的牌不出现一次以上的移动，应该就是最少的了

quanliking

[quote]原帖由 "chenjn"]我觉得只要在A1-An任何一个地方和相邻的牌不出现一次以上的移动，应该就是最少的了[/quote 发表：
     

我觉得这道题，仔细分析一下，就比较简单了，而且感觉题目出的不够灵活，chenjin 的算法应该没有问题。
思路大致如下：
首先得满足其中一个边界，如 cards [0], 只能通过和右边的 cards [1] 交换牌数来实现，得到满足后，就不必理会 cards [0]了，边界自然就变成了cards [1], 问题的范围缩小，依此类推，很显然用递归算法是很容易实现的。

下面是自己编着玩的另外一种类似方法，同样是递归实现，刚开始学编程，多包含：

1. 
   
2. /* 采用递归算法 */
   
3. #include <stdlib.h>;
   
4. #define HEAP 6         /* 堆数,自行修改 */
   
5. #define AVERAGE 10      /* 平均每堆牌数 */
   
6.                                                                                 
   
7. int move( int [], int);
   
8.                                                                                 
   
9. int main()
   
10. {
    
11.         int cards [ HEAP ] = { 8, 9, 13, 6, 9, 15 };
    
12.                                                                                 
    
13.         int i;
    
14.         printf ( "Before move:\n");
    
15.         for ( i = 0; i <= HEAP -1; i++)
    
16.                 printf ( "%d ", cards [i] );
    
17.                                                                                 
    
18.         printf ("\nMoving...\n");
    
19.                                                                                 
    
20.         printf ( "Move steps: %d\nAfter Move:\n\
    
21. ", move ( cards, HEAP ));
    
22.                                                                                 
    
23.         for ( i = 0; i <= HEAP -1; i++)
    
24.                 printf ( "%d ", cards[i]);
    
25.         printf ("\n");
    
26. }
    
27.                                                                               
    
28. int move ( int c [], int size)  /* 模拟传引用， 递数组和大小 */
    
29. {
    
30.         static count = 0;       /* 统计步数 */
    
31.                                                                               
    
32.         if ( size == 1 )
    
33.                 return count;
    
34.                                                                               
    
35.         else {
    
36.                 int n;
    
37.                 n = size/2;     /* 把数组拆成两块，取前 n 堆牌 */
    
38.                                                                               
    
39.                 int i;
    
40.                 int foresum = 0;
    
41.                 for ( i = 0; i <= n-1; i++) /* 计算前 n 堆牌总数 */
    
42.                         foresum += c[i];
    
43.                                                                               
    
44.                                                                               
    
45.                 if ( foresum >; n * AVERAGE ) {
    
46.                         c[n-1] -= foresum - n * AVERAGE;
    
47.                         c[n] += foresum - n * AVERAGE;
    
48.                         count += 1;
    
49.                 }
    
50.                                                                               
    
51.                 else if ( foresum < n * AVERAGE ) {
    
52.                         c[n-1] += n * AVERAGE - foresum;
    
53.                         c[n] -= n * AVERAGE - foresum;
    
54.                         count += 1;
    
55.                 }
    
56.                                                                               
    
57.                 for ( i = 0; i <= HEAP -1; i++)
    
58.                 /* 打印每次移动后结果, 这里感觉有问题，请指点 */
    
59.                         printf ( "%d ", c[i]);
    
60.                 printf ("\n");
    
61.                                                                               
    
62.                 move ( c, n ); /* 递归开始 */
    
63.                 move ( &c[n], size - n );
    
64.         }
    
65.                                                                               
    
66. }
    

复制代码

xa_butterfly

想法很好.偶是想不出来

yg

这个算法不能保证最优

yuxq

说的详细些，把你的具体意见写出来大家一块讨论

JohnBull

用A*算法搜索，启发函数设置为均方差。
每步都尽量让均方差降到最小。