回 帖 发 新 帖 刷新版面

主题:[经典的算法题分享][原创]高手是怎样练成的---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个回复)

91 楼


都是算法设计与分析上面的题吧,好多

92 楼


是王晓东吗?
是我们的老师呀..呵呵,,,.[em2]

93 楼

请问你买的书名是?

94 楼


请问这本算法名字是什么呢?谢谢!

95 楼

请教4.18 怎么做啊?

96 楼

真是辛苦了
我好好研究一下
再和你交流

97 楼

在下第一题

#include<iostream.h>
void main()
{
    int a[10]={0};   //保存页数的数列
    int N;
    cin>>N;

    int n;

    //**********
    for(int i=1;i<=N;i++)
    {
        n=i;
        //除10得到的余数
        while(n)
        {
            a[n%10]++;
            n=n/10;
        }
    }
    for(int j=0;j<10;j++)
        cout<<a[j]<<endl;
}

98 楼

共有C(26,1)+C(26,2)+C(26,3)+C(26,4)+C(26,5)+C(26,6)

acef

1位  C(26,1)
2位  C(26,2)
3位  C(26,3)
第四位第一个组合是abcd

acef比以ab_..都大有C(26-2,2)
以ac开头的第一位acde
acef比acd_..开头的都大有C(26-4,1)
以ace开头的是acef
C(26,1)+C(26,2)+C(26,3)+C(26-2,2)+C(26-4,1)+1

#include<iostream.h>

int combin(int,int);            //计算C(n,m) 
void main()
{

    int N;
    cin>>N;
    for(int k=1;k<=N;k++)
    {
        char str[6]="";
        cin>>str;

        for(int length=0;str[length];length++);    //求解字符串长度
        int number=0;
        for(int i=1;i<length;i++)
            number+=combin(26,i);

        for(i=0;i<length;i++)
        {
            if(i==0)
                for(int j=1;j<=int(str[0])-'a';j++)
                    number+=combin(26-j,length-i-1);
            else
                for(int j=1;j<=int(str[i])-int(str[i-1])-1;j++)
                    number+=combin('z'-int(str[i-1])-j,length-i-1);
        }
        cout<<++number<<endl;
        
    }


}
int combin(int n,int m)
{
    int molecule=1;            //分子
    int denominator=1;        //分母
    for(int i=1;i<=m;i++)
    {
        molecule*=n-i+1;
        denominator*=i;
    }
    return molecule/denominator;

}

99 楼

第3题


36分解因数
36=2^2×3^2
36的约数个数是(2+1)×(2+1)=9
把36先分解质因数
再计算个数

#include<iostream.h>
#include<math.h>
void main()
{
    int prime[100];            //素数数列
    //生成素数数列
    //*********************
    prime[0]=2;
    for(int n=3,int i=1;n<=545;n+=2)
    {
        int k=int(sqrt(n));
        int j=3;
        while(j<=k&&n%j)
            j++;
        if(j>k)
            prime[i++]=n;
    }
    //**********************
    int a,b;
    cin>>a;
    cin>>b;

    int div_max=0;            //计算最大的div_max

    for(i=a;i<=b;i++)
    {
        int j=0;
        int div=1;
        int x=i;

        //辗转相除,计算div(x)********
        while(x!=1)
        {
            int num=0;
            while(x%prime[j]==0)
            {
                num++;
                x=x/prime[j];
            }
            j++;
            div*=++num;    
        }
        //*************

        if(div_max<div)
            div_max=div;
    }

    cout<<div_max<<endl;

}

100 楼

大侠,爱死你了

我来回复

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