`
茴香豆
  • 浏览: 132340 次
  • 性别: Icon_minigender_2
  • 来自: 桂林
社区版块
存档分类
最新评论

石子合并问题

阅读更多

问题描述:

  在一个园形操场的四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆。规定

      每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
     
编一程序,由文件读入堆数N及每堆的石子数(20),
      ①
选择一种合并石子的方案,使得做N1次合并,得分的总和最小;
      ②
选择一种合并石子的方案,使得做N1次合并,得分的总和最大。
     
例如,所示的4堆石子,每堆石子数(从最上面的一堆数起,顺时针数)依
     
次为4594。则3次合并得分总和最小的方案:8+13+22=43
     
得分最大的方案为:14+18+22=54

该问题应该用动态规划算法才能得到最优解,而贪心算法得不到最优解。

而动态规划算法的基本要素是:最优子结构和重叠子问题

 

针对该问题,我们用f(i,j)表示从第i堆石子数起,顺时针数j堆石子的得分,则它的动态规划方程为

 当求最大得分总和时

      fij〕=maxfik〕+fxj-k〕+t
     
≤k≤j-1
      c
ij〕=k│ fij〕=fik〕+fxj-k〕+t
     
(2n,1n)

     
当求最小得分总和时
      f
ij〕=minfik〕+fxjk〕+t
     
≤k≤j-1

 

 


      c
ij〕=k│ fij〕=fik〕+fxj-k〕+t
     
(2n,1n)
     
其中x=(ik-1)modn+1,即第i堆数起,顺时针数k+1堆的堆序号。

 

     对每一堆石子来说,它的
      f
i,1〕=0
      c
i,1〕=0 (1≤i≤N
     
对于子序列〔ij〕来说,若求最小得分总和,fij〕的初始值为; 若求最大得分总和,fij〕的初始值为0。(1≤i≤N,2≤j≤N)。

 

例如对例子中的6(3 4 6 5 4 2 )堆石子,按动态规划方程顺推最小得分和。 依次得出含二堆石子的6个子序列的合并方案
      f
〔1,2〕=7 f〔2,2〕=10 f〔3 ,2〕=11
      c
〔1,2〕=1 c〔2,2〕=1 c〔3,2〕=1
      f
〔4,2〕=9 f〔5,2〕=6 f〔6,2〕=5
      c
〔4,2〕=1 c〔5, 2〕=1 c〔6,2〕=1

     
含三堆石子的6(3 4 6 5 4 2 )个子序列的合并方案
      f
〔1,3〕=20 f〔2,3〕=25 f〔3,3〕=24
      c
〔1,3〕=2 c〔2,3〕=2 c〔3,3〕=1
      f
〔4,3〕=17 f〔5,3〕=14 f〔6,3〕=14
      c
〔4,3〕=1 c〔5,3〕=1 c〔6,3〕=2

     
含四堆石子的6(3 4 6 5 4 2 )个子序列的合并方案
      f
〔1,4〕=36 f〔2,4〕=38 f〔3,4〕=34
      c
〔1,4〕=2 c〔2,4〕=2 c〔3,4〕=1
      f
〔4,4〕=28 f〔5,4〕=26 f〔6,4〕=29
      c
〔4,4〕=1 c〔5,4〕=2 c〔6,4〕=3

     
含五堆石子的6(3 4 6 5 4 2 )个子序列的合并方案
      f
〔1,5〕=51 f〔2,5〕=48 f〔3,5〕=45
      c
〔1,5〕=3 c〔2,5〕=2 c〔3,5〕=2
      f
〔4,5〕=41 f〔5,5〕=43 f〔6,5〕=45
      c
〔4,5〕=2 c〔5,5〕=3 c〔6,5〕=3

     
含六堆石子的6(3 4 6 5 4 2 )个子序列的合并方案
      f
〔1,6〕=61 f〔2,6〕=62 f〔3,6〕=61
      c
〔1,6〕=3 c〔2,6〕=2 c〔3,6〕=2
      f
〔4,6〕=61 f〔5,6〕=61 f〔6,6〕=62
      c
〔4,6〕=3 c〔5,6〕=4 c〔6,6〕=3

      f
〔1,6〕是f〔1,6〕,f〔2,6〕,……f〔6,6〕中的最小值,表明最小得分和是由序列〔1,6〕经5次合并得出的。我们从这个序列出发,
     
按下述方法倒推合并过程:
     
c〔1,6〕=3可知,第5次合并的两堆石子分别由子序列〔1,3〕和子序列〔4,3〕经4次合并后得出。其中c〔1,3〕=2可知由子序列〔1,3〕合并成的一堆石子是由子序列〔1,2〕和第三堆合并而来的。而c〔1,2〕=1,以表明了子序列〔1,2〕的合并方案是第1堆合并第2堆。
     
由此倒推回去,得出第1,第2次合并的方案,每次合并得分
     
第一次合并 3 4 6……    ->
     
第二次合并 7 6……          ->13
     
13……
     
子序列〔1,3〕经2次合并后合并成1堆, 2次合并的得分和=7+13=20。
     
c〔4,3〕=1,可知由子序列〔4,3〕合并成的一堆石子是由第4堆和子序列〔5,
     
2〕合并而来的。而c〔5,2〕=1,又表明了子序列〔5,2〕的合并方案是第5堆合并第6堆。由此倒推回去,得出第3、第4次合并的方案
     
每次合并得分:
      
第三次合并 ……54 2     ->
     
第四次合并 ……5 6        ->11
      ……
11
     
子序列〔4,3〕经2次合并后合并成1堆,2次合并的得分和=6+11=17。
     
第五次合并是将最后两堆合并成1堆,该次合并的得分为24。
     
显然,上述5次合并的得分总和为最小
     
20+17+24=61

 

 

下面分析下代码的实现过程

 1.初始化grades和ks的值

  /*

初始化Grades和ks的值
choice为1表示求最多得分,为0为求最少得分
n表示有n堆石子
  */
void init(int **grades,int **ks,int choice,int n){
	//给计算得分的数组赋初值
	if(choice==1){
		for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
               grades[i][j]=0;
               ks[i][j]=0;
			}
		}	
	}else{
       for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
				if(j==1){ 
					grades[i][j]=0;
				}else{
                    grades[i][j]=999999;
				}
               ks[i][j]=0;
			}
		}	
	}
}

  2.计算子问题的最少得分

  /*

  计算从start堆开始,计算count堆石子的最少得分
  stoneCounts储存所有堆的石子数
  leastGrades[start,count]对应的最少得分
  ks[start,count]记录第start到第start+count间的k值,1=<k<=(count-1)
  */
void  getMiniGrade(int *stoneCounts,int **leastGrades,int **ks,int start,int count,int n){
	if(count>1){
		int countStones=0;
		//计算石子数
		for(int j=0;j<count;j++){
           countStones=countStones+stoneCounts[start+j];
		}
		int grade=999999;
		for(int i=1;i<count;i++){
			 int k=(start+i-1)%n+1;
			// cout<<" 中间值:"<<i<<">>>>"<<leastGrades[start][i]<<"    k:"<<k<<"   "<<leastGrades[k][count-i]<<endl;
		     int newgrade=leastGrades[start][i]+leastGrades[k][count-i]+countStones;
			 //cout<<"最小成绩:"<<newgrade<<endl;
			 if(newgrade<grade){
                 grade=newgrade;
				 ks[start][count]=i;
			 }
		}
        leastGrades[start][count]=grade;
		//cout<<"start::"<<start<<"最小值:"<<leastGrades[start][count]<<"   c的值:"<<ks[start][count]<<endl;
	}
}

 3.计算所有子问题的最少得分

  /*

 计算所有子问题的最少得分
  */
void getEachMiniGrades(int *stoneCounts,int **leastGrades,int **ks,int n){
	for(int j=2;j<=n;j++){
		for(int i=1;i<=n;i++){
          getMiniGrade(stoneCounts,leastGrades,ks,i,j,n);
		}
	}
}

 4.获得最少得分

   /*

  获得最少得分
  */
int miniGrade(int *stoneCounts,int **leastGrades,int **ks,int n){
	getEachMiniGrades(stoneCounts,leastGrades,ks,n);
   int mini=999999;
   for(int i=1;i<=n;i++){
      int newMini=leastGrades[i][n];
	  if(newMini<mini){mini=newMini;}
   }
   return mini;
}

  5.计算子问题的最多得分

   /*

  计算从start堆开始,计算count堆石子的最多得分
  */
void getMaxGrades(int *stoneCounts,int **maxGrades,int **ks,int start,int count,int n){
     	if(count>1){
		int countStones=0;
		//计算石子数
		for(int j=0;j<count;j++){
           countStones=countStones+stoneCounts[start+j];
		}
		int grade=0;
		for(int i=1;i<count;i++){
			 int k=(start+i-1)%n+1;
		     int newgrade=maxGrades[start][i]+maxGrades[k][count-i]+countStones;
			 if(newgrade>grade){
                 grade=newgrade;
				 ks[start][count]=i;
			 }
		}
        maxGrades[start][count]=grade;
	}
}

 6.计算每个子问题的最多得分

  /*

 计算所有子问题的最多得分
  */
void getEachMaxiGrades(int *stoneCounts,int **maxGrades,int **ks,int n){
     for(int j=2;j<=n;j++){
		for(int i=1;i<=n;i++){
          getMaxGrades(stoneCounts,maxGrades,ks,i,j,n);
		}
	}
}

  7.获得最多得分

  /*

  获得最多得分
  */
int maxGrade(int *stoneCounts,int **maxGrades,int **ks,int n){
   getEachMaxiGrades(stoneCounts,maxGrades,ks,n);
   int max=0;
   for(int i=1;i<=n;i++){
      int newMax=maxGrades[i][n];
	  if(newMax>max){max=newMax;}
   }
   return max;
}

  8.显示每堆石子的数量

   /*

显示各堆石子的数量
  */
void showStones(int *stoneCounts,int n){
	cout<<"各堆石子数:"<<n<<endl;
	int count=0;
	for(int i=1;i<=(n-1);i++){
     count++;
	 cout<<stoneCounts[i]<<"\t";
	 if(count==6){count=0;cout<<endl;}
	}
   cout<<endl;
}

 9.显示所有子问题的得分情况

   /*

显示各子问题所得分数
  */
void showGrades(int **grades,int n){
   cout<<"所得分数:"<<endl;
   for(int i=1;i<=n;i++){
	   for(int j=1;j<=n;j++){
         cout<<grades[i][j]<<"\t";
	   }
	   cout<<endl;
   }
   cout<<endl;
}

 10.main函数的内容

     void main(){

   FILE *fin,*fout;
   int n,*stoneCounts,**leastGrades,**maxGrades,**ksMini,**ksMax;
   if((fin=fopen("input2.txt","r"))==NULL)   
		printf("Read error!!");
   fscanf(fin,"%d",&n);
   fclose(fin);

    stoneCounts =new int [2*n];
	
    leastGrades = (int **)malloc((n + 1) * sizeof(int *));
    maxGrades =(int **)malloc((n + 1) * sizeof(int *));
    ksMini =(int **)malloc((n + 1) * sizeof(int *));
    ksMax=(int **)malloc((n + 1) * sizeof(int *));
    for(int i = 0; i<= n; i++){
    leastGrades[i] = (int *)malloc((n + 1) * sizeof(int));
    maxGrades[i] = (int *)malloc((n + 1) * sizeof(int));
	ksMini[i] = (int *)malloc((n + 1) * sizeof(int));
	ksMax[i] = (int *)malloc((n + 1) * sizeof(int));
	}

   init(leastGrades,ksMini,0,n);
   init(maxGrades,ksMax,1,n);
    
   if((fin=fopen("input2.txt","r"))==NULL)   
		printf("Read error!!\n");
   fscanf(fin,"%d",&n);
   for(int j=1;j<=n;j++){
     fscanf(fin,"%d",&stoneCounts[j]);
   }
   fclose(fin);
   for(int k=n+1;k<=(2*n-1);k++){
     stoneCounts[k]=stoneCounts[k-n];
   }
  showStones(stoneCounts,2*n);
  int mini=miniGrade(stoneCounts,leastGrades,ksMini,n);
  cout<<"最少得分的子问题:"<<endl;
  showGrades(leastGrades,n);
  int max=maxGrade(stoneCounts,maxGrades,ksMax,n);
   cout<<"最多得分的子问题:"<<endl;
  showGrades(maxGrades,n);
  cout<<"最小值:"<<mini<<"最大值:"<<max<<endl;
  fout=fopen("output2.txt","w");
  fprintf(fout,"%d\n",mini);
  fprintf(fout,"%d\n",max);
  fclose(fout);
}

 

 

  源代码和对石子合并问题的详细解说文档在上上传文件里

分享到:
评论
1 楼 sfeeq 2011-03-17  
分析的很透彻,非常感谢!

相关推荐

    石子合并问题的 动态规划解法

    //--石子合并问题 /*问题描述:在一个圆形操场的四周摆放着n堆石子,先要将石子有序的合并为一堆。规定每次只能选相邻的石子合并成一堆,并将新一堆的石子数 记录为该次合并的得分。试设计一个算法,记录n堆石子...

    算法设计与分析:石子合并问题

    《算法设计与分析:石子合并问题》 石子合并问题是一个典型的动态规划问题,它源于实际生活中的操作,如游戏或资源优化等场景。在这个问题中,我们面临一个圆形操场上的n堆石子,目标是通过相邻两堆石子的合并,...

    【算法设计分析课程设计】动态规划解决石子合并问题及回溯法解决运动员匹配问题

    针对石子合并问题,本文利用动态规划算法寻求石子合并时的最大,最小得分,选择相邻的两堆石子堆进行合并,其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程,利用程序进行求解。算例结果...

    动态规划 解决石子合并问题

    动态规划 解决石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出...

    动态规划解石子合并问题

    在这个“石子合并问题”中,我们面临的就是这样一个挑战。问题描述可能涉及在环形排列的石子上进行一系列合并操作,每次操作可以将相邻的两堆石子合并成一堆,消耗一定的能量。目标可能是最小化完成所有合并操作所需...

    石子合并 问题 动态规划 源码

    用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题

    石子合并问题代码

    算法分析课程作业,C语言编写,可能需要用input.txt输入,石子合并问题代码

    石子合并问题可运行Java源码

    石子合并问题可运行Java源码,下载到Eclipse就可以运行了。 要求在工程根目录下有input.txt文件,结果output.txt会生成在相同目录下

    实现3-3石子合并问题.cpp

    实现3-3石子合并问题.cpp

    石子合并问题 用动态规划方法

    ### 石子合并问题与动态规划 #### 一、问题背景及定义 在计算机科学领域,特别是算法设计中,石子合并问题是常见的一个问题。该问题通常可以这样描述:假设有一行排布的N个石子,每个石子有一个特定的分数。玩家的...

    石子合并 在一个圆形操场的四周摆放着 n 堆石子. 现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, 并将新的一堆石子数记为该次合并的得分.

    ### 石子合并问题解析与算法实现 #### 知识点概述 石子合并问题是在计算机科学领域中一种经典的动态规划问题,它涉及到数组、循环、动态规划算法以及位运算等核心概念。在这个问题中,我们需要在一个圆形操场的...

    C语言实现的石子合并问题

    C语言实现的石子合并问题,自己可以改成其他的语言,这是核心语句

    石子合并问题JAVA源代码

    ### 石子合并问题分析与Java实现 #### 一、问题背景及定义 在一个圆形操场的四周摆放着\( n \)堆石子。任务是将这些石子有序地合并成一堆。每次只能选择两堆相邻的石子进行合并,新合并的一堆石子数为这两堆石子数...

    1137: 石子合并问题

    规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...

    石子合并问题共1页.pdf.zip

    标题中的“石子合并问题”通常是指一个计算机科学或算法设计中的经典问题,它与数据结构和动态规划等基础知识紧密相关。在这个问题中,我们通常想象有若干堆石子,每堆有不同的数量,两个玩家轮流从任一堆中取走一定...

    算法设计——石子合并问题

    ### 算法设计——石子合并问题 #### 背景介绍 在算法设计领域,特别是针对优化问题的研究中,“石子合并问题”是一种典型的动态规划应用案例。该问题通常表述为:在一个直线上放置若干堆石子,每堆石子的数量已知。...

Global site tag (gtag.js) - Google Analytics