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

81 楼

sufeiyu [专家分：50] 发布于 2007-11-01 17:40:00

这本书叫《算法设计与分析实验题解》

82 楼

hzszzlf [专家分：0] 发布于 2007-11-13 23:19:00

这是本什么书啊?

83 楼

sunxiaopi [专家分：0] 发布于 2007-11-17 10:22:00

好多阿！！辛苦你了~~

84 楼

hy_hslcn [专家分：0] 发布于 2007-11-19 18:12:00

// Counting1.1.cpp
//

#include "stdafx.h"
#include <assert.h>
#include <cmath>
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int gMaxPages=0;
int gNumberCount[10]={0};
vector<short> gBitContainer;

/* compute number:0 ---> nBottom * 10^nIndex */
void CountNumberInInteger(int nIndex,int nBottom)
{
    assert(nIndex>=0 && nBottom>=1 && nBottom<=9);

    if(nIndex==0)       //count:0-9
    {
        for(int i=0;i<nBottom;++i)
            gNumberCount[i]+=1;
    }
    else             //count:10-10^n
    {
        int nPowerOfTen=(int)pow(10,nIndex);
        for(int i=0;i<=9;++i)
        {
            if(i<nBottom)
                gNumberCount[i]+=nBottom*nIndex*nPowerOfTen/10+nPowerOfTen;
            else
                gNumberCount[i]+=nBottom*nIndex*nPowerOfTen/10;
        }
    }
}

/*store each bit number into gBitContainer*/
void GetEachBitNumber()
{
    assert(gMaxPages>0);

    gBitContainer.clear();

    int nSum=gMaxPages;
    while(nSum)
    {
        gBitContainer.push_back(nSum%10);
        nSum/=10;
    }
}

/*Input  :   the maximum number of pages.
  Output :   get each number's count    */
void CountNumberInAllPages()
{
    GetEachBitNumber();

    if(gBitContainer.empty())
        return;

    int nSum=gMaxPages;
    int nElements=gBitContainer.size();

    //count in ten's multiple
    for(int i=nElements-1;i>=0;--i)
    {
        int nBottom=gBitContainer.at(i);
        if(nBottom)
            CountNumberInInteger(i,nBottom);

        nSum-=nBottom*(int)pow(10,i);
        gNumberCount[nBottom]+=nSum+1;
    }

    //erase plus zero
    int nIndex=nElements-1;
    while(nIndex>=0)
    {
        gNumberCount[0]-=(int)pow(10,nIndex);
        nIndex--;
    }
}

/*print show times of each number*/
void PrintResult()
{
    cout<<"Count of "<<gMaxPages<<":\n";
    for(int i=0;i<10;++i)
        cout<<'<'<<i<<'>'<<"  "<<gNumberCount[i]<<endl;
}

int main(int argc, char* argv[])
{
    cout<<"Please input the number of pages:\n";
    cin>>gMaxPages;

    CountNumberInAllPages();
    PrintResult();

    return 0;
}

85 楼

manaburn [专家分：250] 发布于 2007-11-24 13:27:00

开始做,从第一题开始...

#include <iostream>

using namespace std;

int counts[10]={0};

void count(int);
void compute(long int);
void elementCount(long int);
void displayCount(void);

int main()
{
    long int number;
    cout << "please input a number : ";
    cin >> number;
    compute(number);
    displayCount();


    system("pause");
    return 0;
}

void displayCount(void)
{
     for(int i=0;i<10;i++)
     {
             cout<< i << " counts is " << counts[i] << endl;
     }
}
void compute(long int number)
{
     for(int i=1 ;i<=number;i++)
     {
             elementCount(i);
     }
}

void elementCount(long int number)
{
     int residue = 0;

     while(number)
    {
         residue = number%10;
         number = number/10;
         count(residue);
    }
}

void count(int num)
{
     counts[num]++;
}

86 楼

hy_hslcn [专家分：0] 发布于 2007-11-25 16:29:00

// 1.2   Dictionary
//
/////////////////////
#include "stdafx.h"
#include <assert.h>
#include <iostream>
#include <string>
using namespace std;

string g_strLetters;   //store input letters
int gTableF[6][27]={0};    //Fm(n)
int gTableS[6]={0};        //Sm(n)

void FillStringCountTable()
{
    //fill table: gTableF[m][n] (m:1->5, n:1->26)
    int m=0,n=0,t=0;

    for(n=1;n<=26;++n)    //m=1
        gTableF[1][n]=n;

    for(m=2;m<=5;++m)     //m=n
        gTableF[m][m]=1;

    for(m=2;m<=5;++m)     //m>1 & m!=n
        for(n=m+1;n<=26;++n)
        {
            gTableF[m][n]=0;
            for(t=m-1;t<=n-1;++t)
                gTableF[m][n]+=gTableF[m-1][t];
        }
}

void FillSumCountTable()
{
    //fill table: gTableS[m][n] (m:0->5, n=26)
    gTableS[1]=26;

    for(int m=2;m<=5;++m)
    {
        gTableS[m]=0;
        for(int t=1;t<=m;++t)
            gTableS[m]+=gTableF[t][26];
    }
}

int GetOrderInDictionary(int index)
{
    assert(index>=0 && index<=5);

    if(index==0)
        return g_strLetters[index]-96;

    int    nCode=gTableS[index]+1;

    //compute dictionary code
    for(int t=0;t<index;++t)
    {
        //make sure the up letter order
        assert(g_strLetters[t]-97>=t);

        if(g_strLetters[t]-97==t)
            continue;

        for(int i=0;i<g_strLetters[t]-97-t;++i)
            nCode+=gTableF[index-t][25-t-i];
    }

    nCode+=g_strLetters[index]-index-97;
    return nCode;
}

int main(int argc, char* argv[])
{
    g_strLetters.resize(7,0);
    FillStringCountTable();
    FillSumCountTable();

    do
    {
        cout<<"Please input a string(size<6): ";

        int i=0;
        char chInput=0;
        while((chInput=getchar())!='\n')
        {
            assert(chInput>=97 && chInput<=122);

            if(i<6)
                g_strLetters[i++]=chInput;
        }

        cout<<"Input string:    "<<g_strLetters<<endl;
        cout<<"Dictionary code: "<<GetOrderInDictionary(i-1)<<"\n\n";
        cout<<"<enter 'q' to exit,others go on...>";
    }
    while(getchar()!=113);    //enter 'q' to exit
    return 0;
}

87 楼

mglyyujing [专家分：0] 发布于 2008-01-01 13:38:00

谁有算法设计习题解的电子书，可以给我发一下吗？我的QQ是570704682，不胜感激！

88 楼

kingofmiaomiao [专家分：0] 发布于 2008-01-04 11:08:00

有没有直接下载的啊,我想留一本保存耶:P

89 楼

wang1ying09 [专家分：0] 发布于 2008-01-07 18:46:00

看到有这么多的东西，不回不行的啊！

90 楼

qzp19880502 [专家分：20] 发布于 2008-01-08 19:17:00

算法实现题1-2 字典序问题
我们网站上有一道这样的题，能把代码发给我吗？

我来回复

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

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

回复列表（共110个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

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

回复列表 （共110个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共110个回复）