回 帖 发 新 帖 刷新版面

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

[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]

回复列表 (共110个回复)

71 楼


《算法设计与分析实验题解》
收到,谢啦楼主

72 楼

统计数字问题答案:
#include "stdio.h"
/*在源程序所在目录下新建一TXT文件input.txt,并在input.txt输入页码然后保存,新建output.txt*/
main()
{
 FILE *fp; 
 char ch,*p="";  
 int i=0,pg[10],t=0,j;
 for(j=0;j<10;j++)
 pg[j]=0;
 if((fp=fopen("input.txt","r"))==NULL)
     {
         printf("cannot open this file \n");
     }
 while ((ch=fgetc(fp))!=EOF)
 {
     i=i*10+ch-48;
 }
 for(j=1;j<=i;j++)
 {
     t=j;
     while(t)
     {
         switch(t%10)
         {
             case 0:
             pg[0]++;break;
             case 1:
             pg[1]++;break;
             case 2:
             pg[2]++;break;
             case 3:
             pg[3]++;break;
             case 4:
             pg[4]++;break;
             case 5:
             pg[5]++;break;
             case 6:
             pg[6]++;break;
             case 7:
             pg[7]++;break;
             case 8:
             pg[8]++;break;
             case 9:
             pg[9]++;break;
         }
         t=t/10;
     }
 }
 fp=fopen("output.txt","w");
 for(i=0;i<10;i++)
      fprintf(fp,"%d:%d\n",i,pg[i]);
 fclose(fp);
 fp=fopen("output.txt","r");
 while ((ch=fgetc(fp))!=EOF)
 {
         printf("%c",ch);
 }
}
本人对C了解不深,其中不足之处还请各位高手多多指点。

73 楼

楼主是否有电子版?
能否将书发到我的邮箱fymsn@sohu.com
谢谢

74 楼

没有电子版

75 楼


可以发一份资料到pdpdp@tom.com上吗,谢谢了

76 楼


可以发一份给我吗?谢谢
gaer185@126.com

77 楼

晕到。。。。
发什么?????

78 楼

楼主 我为你的精神而感动,我可是从第一页一直看到第8页,哇,提倡看贴要看仔细啊,明明楼主早就说书名了,还好多人在一个劲的问书名,真是郁闷。
   我准备先把钱能的C++看玩在做楼主给题目o(∩_∩)o...。因为文件那一块我还不太会。
  楼主加油。~~~~~~~~~~~~~~

79 楼

//算法实现题1-1 统计数字问题
#include<stdio.h>
void main()
{
    int i,n,count[10],a,b;
    scanf("%d",&n);
    for(i=0;i<10;i++)
        count[i]=0;
    for(i=1;i<=n;i++)
    {
        a=i;
        while(a)
        {
            b=a%10;
            a/=10;
            count[b]++;
        }
    }
    for(i=0;i<10;i++)
        printf("%d\n",count[i]);
}

80 楼

//算法实现题1-3 最多约数问题

#include<stdio.h>
#include<math.h>

int divPrime(int n)
{
    int a,i,sum;
    a=sqrt(n);
    if(n==1)
        return 1;
    else
        sum=2;
    for(i=2;i<a;i++)
    {
        if(!(n%i))
            sum+=2;
    }
    if(a*a==n)
        sum++;
    return sum;
}

void main()
{
    int a,b,i,max,sum;
    max=0;
    scanf("%d %d",&a,&b);
    for(i=a;i<=b;i++)
    {
        sum=divPrime(i);
        if(sum>max)
            max=sum;
    }
    printf("%d\n",max);
}

我来回复

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