[原创]排序算法的经典应用实例

主题：[原创]排序算法的经典应用实例

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

        [color=FF0000]排序算法的经典应用实例[/color]

    [color=FF00FF]说明:[/color] 本文摘自:[url=http://acm.5d6d.com]http://acm.5d6d.com[/url]

    [例1]    由文件给出N个1到30000间无序正整数，其中1<=N<=10000,同一个正整数
    可能会出现多次，出现次数最多的整数称为众数。

    [编程任务]：求出该文件中的众数M及它出现的次数num。

    [输入格式]：两行，第一行为正整数的个数N，第二行为各个正整数T。

    [输出格式]：两行，第一行为众数M，第二行为众数M出现的次数num。

    [样例输入]
            10
            2     3     4    5    3    3    4    5    6    3
    [样例输出]
            3
            4


    [例2]    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个n口井
    的油田，每口油井都要有一条输油管道沿最短路径（或南或北）与主管道相连，如
    图所示：
    ===============================================================
                |
                |                              |
        ------|-----------|----------|------------|-----------  <----主输油管道
           | <---输油管道          |
           。<---油井
        y
        i
        i
        i/------------>x
    ==============================================================
    如果给定n口油井的位置，即它们的X坐标和Y坐标，应如何确定主管道的最优
    位置，使各油井到主管道之间的输油管道长度总和为最小？

    [编程任务]：求出主管道的最优位置。

    [输入格式]：第一行，油井数量N；
                   第二到N+1行每行对应一个油井的坐标经X，Y。
    [输出格式]：一行，最优位置的坐标（X，Y）。


    [例3]    有n 个人在一个水龙头前排队接水，每个人接水的时间Ti是互不相等的。

    [编程任务]：找到一种这n个人排队的顺序，使他们平均等待时间达到最小。

    [输入格式]：两行，第一行为：排队人数n ;
            第二行为：分别为每个人的等待时间Ti，每个数据用一空格隔开。
    [输出格式]：一行，即为这n个人排队的最优顺序。



    [例4]    现有n个正整数，n<=10000，要求出这n个正整数中的第k个最小整数（相
    同大小的整数只计算一次），k<=1000，正整数均小于65535。

    [编程任务]：求出第k个最小整数。

    [输入格式]：第一行为：正整数的个数n和k ;
                   第二行为： n个整数，每个整数之间用空格隔开。

    [输出格式]：第k 个最小正整数，若无解，则输出“NO ANSWERS” 。

    [样例输入]：
            10   3
            1  3   3  7  2  5   1   2   4   6

    [样例输出]：
            3



    [例5]    竞赛排名。某市组织一次中学生科技全能竞赛，每个选手要参加数学、物理
    、天文、地理、生物、计算机和英语共八项竞赛，最后综合八项竞赛的成绩排出总
    名次。选手编号依次为：1,2,. . . ,n（其中n为参赛总人数）。
        设xij表示编号为i的选手第j项竞赛成绩（ 1<= j <= n , 1 <= j <= 8 ）。其它
    指标如下：
    （1）第j项竞赛的平均分 avg(j) (其中1<= j <= 8 );
    （2）选手i的总分sum(i) ;

    [编程任务]：做出一个排名表。



[url]http://acm.5d6d.com[/url]

最后更新于：2007-05-29 07:20:00

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

回复列表（共4个回复）

沙发

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

参考解答如下:

===================NO.1=====================
[code]

    /***********************************
     Soulation: find the zhongsu !!!

     name : zhongsu.c

     time :  2007/5/12

     Input :
        5 2
        2 3 2 2 3

     Output: 2 3

     ***********************************/

    #include <stdio.h>
    #include <stdlib.h>

    #define MAX_NUM     10001

    int main(void)
    {
        int N,i;
        int a[MAX_NUM],b[3*MAX_NUM] ;
        int max = 0,best_n=0,best_t=0 ;

        memset(a, 0 , sizeof(a) ) ;
        memset(b, 0 , sizeof(b) ) ;

        scanf("%d",&N ) ;
        for(i=1 ; i<= N ; i++)
        scanf("%d",&a[i]) ;

        /* get the max num */

        for(i=1 ; i<= N ; i++)
        if ( a[i] > max )
        max = a[i] ;

        /* begin to count the times */

        for(i=1; i<= N ; i++)
        b[a[i]] ++ ;

        /* find the best num ,which is zhongsu !!! */

        for(i=1; i<= max ; i++)
        if(b[i] > best_t)
        {
            best_t = b[i] ;
            best_n = i ;
        }

        /* Output the message */

        printf("%d\n%d\n",best_n,best_t) ;

        return 0 ;
    }




[/code]

板凳

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

====================NO.2======================
[code]

    /************************************
     Can do : dev a best suyouguangdao !!!
     name : soyou.c
     time : 2007/5/12

     Input :

      Output:

     ************************************/

     #include <stdio.h>
     #include <stdlib.h>
     #include <ctype.h>
     #include <string.h>
     #include <math.h>

     #define MAXN    101

     int main(int argc, char *argv[])
     {
        float x[MAXN]={0},y[MAXN]={0} ;
        int i,j,k,n ;
        float maxy= -100001.0, miny=100001.0 ;
        float besty ,h;
        /* Read the data */

        scanf("%d",&n) ;
        for(i=1 ;i <= n ; i++)
        scanf("%f %f",&x[i],&y[i]) ;

        /* Find the max y and max x !!! */

        for(i=1 ; i<= n ; i++)
        {
            if (y[i] > maxy )
            maxy = y[i] ;
            if (y[i] < miny )
            miny = y[i] ;
        }

        /* For search  all the situlation !!! */

        besty = (maxy+miny) / 2 ;

        /* output the ans */

        printf("\nmaxy = %f \n miny = %f\n",maxy, miny) ;

        printf("%f\n",besty ) ;

        printf("\n====================\n") ;

        float  good = 100001,sum ,goody = 0;

        for(h = miny ; h<=maxy ; h+=0.0001)
        {
            sum = 0 ;
            for(i=1 ; i<= n ; i++)
            sum += fabs(y[i]-h) ;
            if ( sum < good )
            {
                good = sum ;
                goody = h ;
            }
        }

        printf("\ngoody = %f\n",goody) ;

        return 0 ;
    }






[/code]

3 楼

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

======================NO.3=======================
[code]

    /************************************
     what : sort and find the best paidui fanshi
     name : paidui.c
     time : 2007/5/12

     Input : 4
         3 2 1 4
     Output:
         1 2 3 4
         1+3+6+10=20
     Sn = sum {n1=m1,n2+n1=m2,n3+n2+n1=m3 ... }
     ==> sum { m1=n1,m2=n2+m1,m3=n3+m2...)

     ************************************/

     #include <stdio.h>

     #define MAX_N     10001

     int main(void)
     {
        int a[MAX_N]={0},N,m[MAX_N]={0} ,b[MAX_N]={0} ;
        int i,j,k,temp,s ;

        /* read the data */

        scanf("%d",&N) ;
        for(i=1 ; i <= N ; i++)
        scanf("%d",&a[i]) ;

        /* begin to insert  sort */

        b[1] = a[1] ;
        s = 1 ;
        for(i=2 ; i<= N ; i++,s++)
        {

            for(j= 1 ; j <= s ; j++)
            if(a[i] < b[j] )
            break ;

            for(k=s ; k >= j ; k--)
            b[k+1] = b[k] ;

            b[j] = a[i] ;
        }

        /* test .... */
        for(i=1 ; i<= N ; i++)
        printf("%d\t",b[i]) ;
        printf("\n") ;
        /* begin to compute the data */

        m[1] = b[1] ;
        long total = b[1];
        for(i=2 ; i<= N ; i++)
        {
            m[i] = b[i] + m[i-1] ;
            total += m[i];
        }

        printf("\ntotal = %ld\n",total ) ;

        return 0 ;
    }


[/code]

4 楼

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

==========================NO.4=====================
[code]

    /********************************
     Cando : find the no.k min num
     name  : numk.c
     time  : 2007/5/12
     Input :
        5 2
        3 1 4 5 6

     Output:
        3
     *********************************/

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

    #define Max 10001

    int main(int argc, char *argv[])
    {

        int a[Max]={0},*t ;
        int i,j,k,n,max=0,num ,ans;

        /* Read the data */

        scanf("%d %d",&n,&k) ;
        for(i=1 ; i<= n ; i++)
        {
            scanf("%d",&a[i]) ;
            if (a[i] > max ) /* get the max num */
            max = a[i] ;
        }

        /* T sort begin... */

        t = (int *) malloc ( sizeof(int) * (max+1) ) ; /* malloc the memory */
        memset ( t , 0 , sizeof(t) ) ;

        for(i= 1 ; i<= n; i++)
        t[a[i]] ++ ;

        num = 0 ;

        for(i=1 ; i<= max ; i++)
        if( 0 != t[i] )
        {
            while (t[i] > 0 )
            {
                num ++ ;
                if(num == k)
                {
                    ans = i ;
                    goto end ;
                }
                t[i] -- ;

            }
        }

        /* Output the result !!! */
        end :
        printf("\nans = %d \n",ans) ;

        return 0 ;
    }


[/code]

我来回复

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

主题：[原创]排序算法的经典应用实例

回复列表（共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：[原创]排序算法的经典应用实例

回复列表 （共4个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共4个回复）