守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 704|回复: 0

[技术资料] 编程算法之分治法

[复制链接]
  • TA的每日心情
    慵懒
    2015-4-16 10:25
  • 签到天数: 8 天

    [LV.3]偶尔看看II

    18

    主题

    19

    帖子

    1284

    积分

    版主

    Rank: 16Rank: 16Rank: 16Rank: 16

    威望
    11
    贡献
    0
    金币
    359
    钢镚
    20
    发表于 2015-4-20 23:24:12 | 显示全部楼层 |阅读模式
    分治算法的基本思想是将一个计算复杂的问题分为若干个问题来进行求解,然后综合各个小问题得到复杂问题的最终答案,如果这些字问题还是比较大,难以解决,可以再把他们分成若干个更小的子问题,直到可以直接求出答案为止。

    一般具有以下特征的问题可使用分治发来求解:
    1 求解问题可以分解成若干个规模较小的相同问题。
    2 求解问题的规模分解到一定程度时,就能够很容易的求解。
    3 合并子问题的解可以得到求解问题的解。
    4 由求解问题所分解出的各个子问题是相互独立的。



    问题来了: 某学校举行乒乓球比赛,在初赛阶段设置为循环赛,设有n位选手参加,初赛共进行n-1天举行。每位选手要于其他每一位选手进行一场比赛,然后按照积分排名选拔进入决赛的选手,规定,每位选手每天必须比赛一场 不能轮空。按此要求为比赛安排具体日程。

    按照分治算法来简化日程的安排,可以将所有参赛选手分为两半,则n个选手的比赛日程可以通过n/2个选手比赛日程来决定,继续用这种一分为二的方法对选手进行划分,知道剩下2位选手时情况就很简单了。

    1. [cpp] view plaincopy

    2.     // 编程算法之分治法.cpp : 定义控制台应用程序的入口点。  
    3.     //  
    4.       
    5.     #include "stdafx.h"  
    6.     #define MAXN 64  
    7.       
    8.     int a[MAXN+1][MAXN+1] = {0};  
    9.       
    10.     void gamecal(int k,int n)  
    11.     {  
    12.         int i,j;  
    13.         if (n==2)  
    14.         {  
    15.             a[k][1] = k;  
    16.             a[k][2] = k+1;  
    17.             a[k+1][1]=k+1;  
    18.             a[k+1][2]=k;  
    19.       
    20.         }  
    21.         else  
    22.         {  
    23.             gamecal(k,n/2);  
    24.             gamecal(k+n/2,n/2);  
    25.             for(i = k;i<k+n/2;++i)  
    26.             {  
    27.                 for(j = n/2+1;j<=n;++j)  
    28.                 {  
    29.                     a[i][j] = a[i+n/2][j-n/2];  
    30.                 }  
    31.             }  
    32.             for(i = k+n/2;i<k+n;++i)  
    33.             {  
    34.                 for(j = n/2+1;j<=n;++j)  
    35.                 {  
    36.                     a[i][j] = a[i-n/2][j-n/2];  
    37.                 }  
    38.             }  
    39.       
    40.         }  
    41.       
    42.       
    43.     }  
    44.     int _tmain(int argc, _TCHAR* argv[])  
    45.     {  
    46.         int m ,i ,j;  
    47.         printf("请输入参赛选手的数量:");  
    48.         scanf_s("%d",&m);  
    49.         j=2;  
    50.         for(i=2;i<8;i++)  
    51.         {  
    52.             j = j*2;  
    53.             if(j==m) break;  
    54.       
    55.         }  
    56.         if(i>=8)  
    57.         {  
    58.             printf("参赛选手必须为2的整数次幂,并且不能超过64\n");  
    59.             return 0;  
    60.         }  
    61.         gamecal(1,m);  
    62.         printf("\n编号");  
    63.         for(i=2;i<=m;++i)  
    64.         {  
    65.             printf("%2d天",i-1);  
    66.         }  
    67.         printf("\n");  
    68.         for(i = 1;i<=m;++i)  
    69.         {  
    70.             for(j=1;i<=m;++i)  
    71.                 printf("%4d",a[i][j]);  
    72.             printf("\n");  
    73.         }  
    74.         system("pause");  
    75.         return 0;  
    76.     }  
    复制代码
    http://blog.csdn.net/yaoyuan0701/article/details/45133635
    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2019-11-21 11:09 , Processed in 0.040957 second(s), 32 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表