分治算法講解-資料下載頁
2025-08-05 03:31本頁面
【正文】 。 (1)每個(gè)選手必須與其他n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能參賽一次； (3)循環(huán)賽在n1天內(nèi)結(jié)束請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n1列的一個(gè)表。在表中的第i行，第j列處填入第i個(gè)選手在第j天所遇到的選手。其中1≤i≤n，1≤j≤n1。假設(shè)有8位參賽選手，8個(gè)選手的比賽日程表如下圖：【思路】按分治的實(shí)現(xiàn)過程，可以先找到上面所示日程表的規(guī)律，即對(duì)角線相等，那么所要完成的操作就是對(duì)角線填充。實(shí)現(xiàn)過程：(1)用一個(gè)for循環(huán)輸出日程表的第一行 for(int i=1。i=N。i++) a[1][i] = i (2)然后定義一個(gè)m值，m初始化為1，m用來控制每一次填充表格時(shí)i（i表示行）和j（j表示列）的起始填充位置。 (3)用一個(gè)for循環(huán)將問題分成幾部分，對(duì)于k=3，n=8，將問題分成3大部分，第一部分為，根據(jù)已經(jīng)填充的第一行，填寫第二行，第二部分為，根據(jù)已經(jīng)填充好的第一部分，填寫第三四行，第三部分為，根據(jù)已經(jīng)填充好的前四行，填寫最后四行。for (ints=1。s=k。s++) N/=2。 (4)用一個(gè)for循環(huán)對(duì)③中提到的每一部分進(jìn)行劃分for(int t=1。t=N。t++)對(duì)于第一部分，將其劃分為四個(gè)小的單元，即對(duì)第二行進(jìn)行如下劃分 同理，對(duì)第二部分（即三四行），劃分為兩部分，第三部分同理。 (5)最后，根據(jù)以上for循環(huán)對(duì)整體的劃分和分治法的思想，進(jìn)行每一個(gè)單元格的填充。填充原則是：對(duì)角線填充 for(int i=m+1。i=2*m。i++) //i控制行 for(int j=m+1。j=2*m。j++) //j控制列 { a[i][j+(t1)*m*2]= a[im][j+(t1)*m*2m]。/*右下角的值等于左上角的值 */ a[i][j+(t1)*m*2m] =a[im][j+(t1)*m*2]。/*左下角的值等于右上角的值 */ }實(shí)例過程： (1)由初始化的第一行填充第二行 (2)由s控制的第一部分填完。然后是s++，進(jìn)行第二部分的填充 (3)最后是第三部分的填充
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1