[经典的算法题分享][原创]高手是怎样练成的---30天搞定最经典的算法训练题（每天必做,不断更新)

主题：[经典的算法题分享][原创]高手是怎样练成的---30天搞定最经典的算法训练题（每天必做,不断更新)

vcacm [专家分：1500] 发布于 2007-04-29 14:00:00

[color=0000FF]
  由于本人最近准备全身心地投入算法学习研究中，幸运地是我买到了一本好书，里面有最经典的算法！
  特别是其中的题目，可为是经典中的“精华”，我想把其中的训练题贴上来和大家一起分享！
  我准备花一个多月的时间把它们搞定，所以我会把我做出来的题目的解答贴在后面！
  同时我也希望大家能把自己做出来了的题目的解答贴上来一起交流！争取找到更好算法！

[/color]
[code]
Algorithm Experiment Problem Set
Xiaodong Wang
(wangxd@fzu.edu.cn)
Department of Computer Science
Fuzhou University P.R.China
February, 2006
[color=FF00FF]Chapter 1 Introduction[/color]
Problem 1.1 Counting
Problem 1.2 Dictionary
Problem 1.3 Divisors
Problem 1.4 Coin Array
Problem 1.5 Maximum Gap
[color=FF00FF]Chapter 2 Recursion and Divide and Conquer[/color]
Problem 2.1 Pipeline
Problem 2.2 Majority
Problem 2.3 Post Office
Problem 2.4 Knight’s Hamilton Tour
Problem 2.5 Half Multiset
Problem 2.6 Half Set
Problem 2.7 Soldiers
Problem 2.8 Permutation with Repetition
Problem 2.9 Lexicographic Order
Problem 2.10 Set Partition
Problem 2.11 Set Partition 2
Problem 2.12 Bicolor Towers of Hanoi
Problem 2.13 Standard 2´n Table
Problem 2.14 Integer Factorization
[color=FF00FF]Chapter 3 Dynamic Programming[/color]
Problem 3.0 Independent Task Scheduling
Problem 3.1 Coin Changing
Problem 3.2 Relation Ordering
Problem 3.3 Counting Powers
Problem 3.4 Edit Distance
Problem 3.5 Pebble Merging
Problem 3.6 Number Triangles
Problem 3.7 Multiplication Table
Problem 3.8 Renting Boats
Problem 3.9 Car Traveling
Problem 3.10 Minimal m Sums
Problem 3.11 Circle Multiplication
Problem 3.12 Maximum Cube
Problem 3.13 Regular Expressions
Problem 3.14 Bitonic Tours
Problem 3.15 Maximum k Multiplications
Problem 3.16 Cheapest Shopping
Problem 3.17 Collecting Samples
Problem 3.18 Optimal Scheduling
Problem 3.19 String Comparison
Problem 3.20 k Median of Directed Trees
Problem 3.21 k Independent Median of Directed Trees
Problem 3.22 k Median of Directed Line
Problem 3.23 2 Median of Directed Line
Problem 3.24 Maximum Connected Component of Trees
Problem 3.25 k Median of Line
Problem 3.26 k Cover of Line
Problem 3.27 m Processors
Problem 3.28 Red Nodes of Red-Black Trees
[color=FF00FF]Chapter 4 Greedy Algorithms[/color]
Problem 4.1 Lecture Halls
Problem 4.2 Optimal Merge
Problem 4.3 Program Storage
Problem 4.4 Optimal Program Storage
Problem 4.5 Program Storage
Problem 4.6 Optimal Services
Problem 4.7 Optimal Many Services
Problem 4.8 d Forest
Problem 4.9 Oiling Car
Problem 4.10 Interval Cover
Problem 4.11 Coin Changing
Problem 4.12 Delete Numbers
Problem 4.13 Maximum Sequence Differences
Problem 4.14 Nesting Boxes
Problem 4.15 Arbitrage
Problem 4.16 Booster Placement
Problem 4.17 Maximum Tape Utilization Ratio
[/code]
[quote]
[color=FF00FF]
全身心研究数据结构与算法设计中。。。
[/color]
[/quote]

最后更新于：2007-05-09 09:53:00

本帖地址： http://bbs.pfan.cn/post/229698.html

回复列表（共110个回复）

31 楼

香脆饼干 [专家分：2040] 发布于 2007-05-01 03:12:00

确实是非常好的题目，比起有些书，都是些数学符号的要亲切的多。最近在学Pascal，就用pascal做了第一道题，多多指教了。

program PageNumber(fin,fout,input,output);

{this program use nIndicator array to track every digits that have been
processed,aIndicator[0] store number of 0s,[1] for number of 1s and so on}

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  fin,fout:TEXT;
  nPages:integer;
  aIndicator:array[0..9] of integer;
  i:integer;

  procedure CountNumber(num:integer;var aIndic:array of integer);
  var
    nLeft:integer;
    nDigit:integer;
  begin
    nLeft:=num;
    while ( not(nLeft=0) ) do
    begin
      nDigit:=nLeft mod 10;             {Get the digit number}
      aIndic[nDigit]:=aIndic[nDigit]+1; {increment the count in the indicator}
      nLeft:=nLeft div 10;              {Get rid of the last digit}
    end;
  end;

begin
  writeln('This program open input.txt for input.');
  assign(fin,'input.txt');
  reset(fin);
  readln(fin,nPages);
  close(fin);

  assign(fout,'output.txt');
  rewrite(fout);

  for i:=1 to nPages do
    CountNumber(i,aIndicator);

  for i:=0 to 9 do
    writeln(fout,aIndicator[i]);

  close(fout);

  writeln('Operation finished successfully!');
  writeln('Go to check output.txt.');
  readln;

end.

32 楼

lshmouse [专家分：10] 发布于 2007-05-01 10:38:00

书的名字是什么??
能不能告诉我们?

33 楼

zjlufo [专家分：20] 发布于 2007-05-01 18:10:00

这个书叫什么名字?

34 楼

vcacm [专家分：1500] 发布于 2007-05-01 20:18:00

前面不是讲了吗？

你们呀。。。
看贴态度不好。。。
《算法设计与分析实验题解》 Write by Wang Xiao Dong !

35 楼

vcacm [专家分：1500] 发布于 2007-05-01 22:11:00

最近由于比较忙。。。。。。

刚刚做了一题：
经典DP问题：
[需要注意它是环状DP，而不是线性DP，所以有两种方法：
  1、转换成线性DP，以空间为代价（空间增长为2N-1）。
  2、摸拟线性进行环状DP（这样比较简单）
  3.当然可以用滚动数组来达到节省空间的效果！（可定义为m[2][MAX])
]
[quote]
=========================================================

算法实现题3-5 石子合并问题
«问题描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只
能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
«编程任务：
对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。
«数据输入：
由文件input.txt提供输入数据。文件的第1 行是正整数n，1<=n <= 100，表示有n堆石子。
第二行有n个数，分别表示每堆石子的个数。
«结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是最小得
分；第2 行中的数是最大得分；。
输入文件示例输出文件示例
input.txt
4
4 4 5 9

output.txt
43
54

=========================================================
[/quote]
[code]
/* * * * * *****************************************
         *
         *    Time : 2007/05/01  Writer: zhxdong
         *    ProblemName : shizi.c
     *
     *    Input : 4
            4 4 5 9
         *    Output:
             43 (min)
            54 (max)
     *
     * * * * * *****************************************/

     #include <stdio.h>

     #define MAX    101

     #define INF    100000001

     int main(int argc, char *argv[])
     {
        FILE *in =fopen ("merge0.in","r") ;
        FILE *out=fopen ("merge0.ans","w") ;
        int m[MAX][MAX]={0,0},w[MAX][MAX]={0,0};
        int data[MAX]={0}, a[MAX]={0} ;
        int i,j,k,r,n,t1,t2,big ;

        long  min = INF , max=0 , sum ;

        fscanf(in,"%d", &n) ;
        fscanf(in,"%d",&a[0]) ;
        for(i=1; i< n; i++)
        {
            fscanf(in,"%d", &data[i] ) ;
            a[i] = a[i-1]+ data[i] ;
        }

        for( k = 1 ; k < n ; k ++ )
        for( i = 0 ; i < n ; i ++ )
        {
             j =  i + k ;

            if ( i == 0 || i == n  )
            sum = a[j%n] ;
            else
            sum = a[j%n]+a[(i-1)%n];

            max = 0 ;
            min = INF ;
            for ( r = i; r< j ; r++ )
            {


                if ((t1 = m[i%n][r%n]+m[(r+1)%n][j%n] + sum ) > max )
                max = t1 ;
                if ( (t2= w[i%n][r%n]+w[(r+1)%n][j%n] + sum ) < min )
                min = t2  ;
            }

            m[i%n][j%n] = max ;
            w[i%n][j%n] = min ;
        }

        fprintf(out,"the max is : %d \n and \n the min is : %d\n",m[0][n-1],w[0][n-1]) ;

        fclose (in) ;
        fclose (out) ;
        return 0 ;
    }

[/code]

36 楼

w_b_d [专家分：50] 发布于 2007-05-01 23:38:00

很好剩下的什么时候发啊期待哦

37 楼

vcacm [专家分：1500] 发布于 2007-05-02 07:57:00

[quote]
很好剩下的什么时候发啊期待哦[/quote]

坚持每天做一点。。。

38 楼

vcacm [专家分：1500] 发布于 2007-05-02 08:12:00

[color=FF00FF]
还有就是：大家可心把自己做出来了的题目的代码发上来，我会为你们的程序进行评测。。。
[/color]

39 楼

vcacm [专家分：1500] 发布于 2007-05-02 10:05:00

为了方便自己测试自己的程序是否确。。。&&  。。。高效。。。
特写了一个简陋的评测程序：
如下：
[code]
/* * * * ================================ * * *
         *
         *      The test of myself !
         *    pn : mytest.c
         *      Time : 2007/5/2 10.00 .am
         *      Write by zhxdong!!!
     *
     * * * * ================================ * * */

    #include <stdio.h>
    #include <string.h>
    #include <time.h>
    #include <memory.h>

    #define MAX_LEN    50

    int main(int argc, char *argv[])
    {
        FILE *res,*tes,*out ;

        int i,j,k ;
        clock_t begin, end ;
        double ok,max;

        const char *test[]={"0","1","2","3","4","5","6","7","8","9"} ;

        char file[MAX_LEN]={'\0'},outt[MAX_LEN]={'\0'},ress[MAX_LEN],tess[MAX_LEN] ;

        char t1[MAX_LEN],t2[MAX_LEN],x1[MAX_LEN],x2[MAX_LEN] ;

        begin = clock() ;

        printf("\nPlease Input the max_time :    ") ;
        scanf("%lf",&max ) ;
        printf("\nAnd input the filename :    ") ;
        scanf("%s",file) ;
        printf("\nAnd input the output result name:    ") ;
        scanf("%s",outt) ;

        printf("\nNow,begin to test...\n") ;
        printf("\nPlease wait a while...\n") ;

        out = fopen(outt,"w+") ;

        fprintf(out,"\n========Your program run result:========= \n") ;
        fprintf(out,"\n######################################\n") ;
        for(i= 0 ; i<= 9 ; i++)
        {
            memset (ress,'\0',sizeof(ress) ) ;
            memset (tess,'\0',sizeof(tess) ) ;

            strcpy (ress,file) ; /* Copy the file name */
            strcpy (tess,file) ;


            strcat (ress,test[i]) ;/* Conncet the test*/
            strcat (tess,test[i]) ;


            strcat (ress,".out") ;
            strcat (tess,".ans") ;


            res = fopen(ress,"r") ;
            tes = fopen(tess,"r") ;

            fprintf(out,"\n==========NO.%d ===========\n",i) ;

            fscanf(tes,"%s",t1 ) ; /* read the test  message */
            fgetc(tes) ;
            fscanf(tes,"%s",t2 ) ;
            fgetc(tes) ;
            fscanf(tes,"%lf",&ok);

            fscanf(res,"%s",x1 ) ;/* read the result message */
            fgetc(res) ;
            fscanf(res,"%s",x2 ) ;
[/code]

40 楼

vcacm [专家分：1500] 发布于 2007-05-02 10:06:00

[code]

            if ( strcmp (t1 , x1)== 0 && strcmp(t2 , x2) == 0 )
            {
                if  (ok <= max )
                fprintf(out,"\nAccept!!!\n") ;
                else
                {
                    fprintf(out,"\nAccept/Run Time Limit!\n") ;
                    fprintf(out,"\nThe max time is : %.0lf",max) ;
                }

                fprintf(out,"\nRun %lf Seconds!!!\n",ok ) ;
            }

            else
            {
                fprintf(out,"\nWrong Answer!!!") ;
                fprintf(out,"\nYour answer: \n%s\n%s\n",t1,t2 ) ;

                fprintf(out,"\nTrue answer: \n%s\n%s\n",x1,x2 ) ;
            }

            fprintf(out,"-------------------------\n") ;

            fclose (tes) ;
            fclose (res) ;
        }
        fprintf(out,"\n######################################\n") ;
        end = clock() ;
        fclose(out) ;
        printf("\nNow,the test is over...\n The result is output the %s file !\n",outt) ;
        printf("\nTotal time is : %lf Seconds!\n",(double)(end-begin)/CLOCKS_PER_SEC) ;

        return 0 ;
    }

[/code]

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：[经典的算法题分享][原创]高手是怎样练成的---30天搞定最经典的算法训练题（每天必做,不断更新)

回复列表（共110个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[经典的算法题分享][原创]高手是怎样练成的---30天搞定最经典的算法训练题（每天必做,不断更新)

回复列表 （共110个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共110个回复）