『壹』 利用分治法設計循環賽日程表的演算法
直接上代碼吧~~
#include<stdio.h>
void (int n);
void tour(int n);
void make(int n);
void odd(int n);
int a[100][100];
int b[100];
int main()
{
int n,i,j;
printf("Please input n :\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
a[1][i]=i;
a[i][1]=i;
}
tour(n);
if(n % 2 == 1)
for(i=1;i<=n;i++)
{
for(j=1;j<=n+1;j++)
{
if(a[i][j] == n +1)
printf(" ");
else
printf("%-4d",a[i][j]);
}
printf("\n");;
}
else
for(i=1;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(a[i][j] == n +1)
printf(" ");
else
printf("%-4d",a[i][j]);
}
printf("\n");;
}
}
void (int n)
{
int m = n/2;
int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
{
a[i][j+m]=a[i][j]+m;
a[i+m][j]=a[i][j+m];
a[i+m][j+m]=a[i][j];
}
}
void tour(int n)
{
if(n==1)
{
a[1][1]=1;
return;
}
if(n%2==1)//奇數
{
tour(n+1);
return;
}
tour(n/2);
make(n);
}
void make(int n)
{
if(n/2>1 && ((n/2)%2))
odd(n);
else
(n);
}
void odd(int n)
{
int i,j;
int m=n/2;
for(i=1;i<=m;i++)
{
b[i]=m+i;
b[m+i]=b[i];
}
for(i=1;i<=m;i++)
{
for(j=1;j<=m+1;j++)
{
if(a[i][j]>m)
{
a[i][j]=b[i];
a[m+i][j]=(b[i]+m)%n;
}
else
{
a[m+i][j]=a[i][j]+m;
}
}
for(j=2;j<=m;j++)
{
a[i][m+j]=b[i+j-1];
a[b[i+j-1]][m+j]=i;
}
}
}
就這個啦，希望能幫到你給分吧~~
『貳』 （急求！）c語言設計：循環賽日程表
循環賽制不一定是n-1天,亦可能是n天.
例如: 當n=3時, 第一天:0-1 第二天 0-2 而此時,1與2還沒有比, 賽事規定: 1必須與2比賽.
/*
當n為偶數時, 分為n/2 和 n/2+1 兩組隊伍, 它們兩組之間完成循環賽事的總時間為 n/2+1天
當n為奇數時, 分為n/2 和 n/2 兩組隊伍, 它們兩組之間完成循環賽事的總時間為 n/2 天
依此來設置列印結果的遞歸.
*/
void theMatchDay(int nStart/*這一組的起始號碼*/,int nTeam/*這一組有多少人*/, int thedayprintf)
{
if(nTeam<=1)
return;
//定義甲乙兩組人數. 甲乙組之間比賽天數為nTeamB
int nTeamA = nTeam/2;
int nTeamB = nTeam - nTeamA;
if(thedayprintf>=nTeamB)
{//還要分組進行.
theMatchDay(nStart,nTeamA,thedayprintf-nTeamB);
theMatchDay(nStart+nTeamA,nTeamB,thedayprintf-nTeamB);
}
else
{
for(int i=0;i<nTeamA;i++)
{
printf("%03d-", nStart+i);
int j = i+thedayprintf;
if(j>=nTeamB) j-=nTeamB;
printf("%03d , ", j+nTeamA+nStart);
}
}
}
void printfMatch(int nteam)
{//列印賽事
for(int i=0;i<nteam;i++)
{
printf("TheDay %d : ",i);
theMatchDay(0,nteam,i);
printf("\n");
}
}
void main()
{
printfMatch(3); //亦可以為其它的.
}
『叄』 循環賽日程演算法的時間復雜度是多少
循環的次數為n*(n-1)/2,所以時間復雜度應該是n^2,即n的平方
『肆』 演算法理解題 循環賽比賽日程表
題目好像有問題。
當n=23=8時？？
應該是：n=2k=8吧！
（1）如果n=2k
循環賽需要進行(n-1)!場比賽。
至少要進行（n-1）天，因為：
①每個選手必須與其他n-1名選手比賽各一次；
②每個選手一天至多隻能賽一次；
③循環賽要在最短時間內完成。
（2）當n=2k=8時，循環賽日程表：
第1天：1-2;3-4;5-6;7-8;
第2天：1-3;2-4;5-7;6-8;
第3天：1-4;2-3;5-8;6-7;
第4天：1-5;2-6;3-7;4-8
第5天：1-6;2-7;3-8;4-5;
第6天：1-7;2-8;3-5;4-6;
第7天：1-8;2-5;3-6;4-7;
『伍』 數據結構---網球循環賽日程表
#include<stdlib.h>
#include<stdio.h>
int **A; //int *指針數組，
int *schele; //int數組，一維數組保存二維數組的數據
int N =1; //問題的規模。初始化時會設定
//isodd:判斷x是否奇數，是則返回1，否則0
int isodd(int x)
{
return x&1;
}
//print:列印賽程
void print()
{
int i,j, row, col;
if(isodd(N))
{
row=N;
col=N+1;
}
else
{
row=N;
col=N;
}
printf("第1列是選手編號\n");
for(i=0;i<row; i++)
{
for(j=0;j<col; j++)
{
printf("%4d", A[i][j]);
}
printf("\n");
}
}
/*init：初始化，設置問題規模N值，分配內存，用schele指向；
把A構造成一個二維數組
*/
void init()
{ int i, n;
char line[100]={'\0'};
printf("請輸入選手人數：");
fgets(line,sizeof(line), stdin);
N=atoi(line);
if(N<=0) exit(-1);
if(isodd(N))
n=N+1;
else
n=N;
//schele是行化的二維數組
schele=(int *)calloc(n*n, sizeof(int));
A=(int **)calloc(n, sizeof(int *));
if(!schele || A==NULL) exit(-2);
for(i=0;i<n;i++) //把A等價為二維數組
{
A[i]=schele+i*n;
A[i][0]=i+1;//初始化這個數組的第一列
}
return;
}
/*replaceVirtual:把第m號虛的選手去掉（換做0）*/
void replaceVirtual(int m)
{
int i,j;
for(i=0;i<m-1;i++) //行：對應選手號1～m-1
{
for (j=0;j<=m;j++) //列: 比行要多1
A[i][j] = (A[i][j]==m)?0:A[i][j];
}
return;
}
/*even:m為偶數時用,由前1組的m位選手的安排，來構成第2組m位選手
的賽程安排，以及兩組之間的比賽安排 */
void even(int m)
{
if(isodd(m)) return;
int i,j;
for (j=0;j<m;j++) //1. 求第2組的安排（+m）
{
for (i=0;i<m;i++)
{
A[i+m][j]=A[i][j]+m;
}
}
for (j=m;j<2*m;j++)//兩組間比賽的安排
{
for (i=0;i<m;i++) //2. 第1組和第2組
{
A[i][j]=A[i+m][j-m]; //把左下角拷貝到右上角
}
for (i=m;i<2*m;i++) //3. 對應的，第2組和第1組
{
A[i][j]=A[i-m][j-m]; //把左上角拷貝到右下角
}
}
return;
}
/*odd:m為奇數時用,由前1組的m位選手的安排，來構成第2組m位選手
的賽程安排，以及兩組之間的比賽安排。這時和m為偶數時的
處理有區別。
*/
void odd(int m)
{
int i,j;
for (j=0;j<=m;j++) //1. 求第2組的安排(前m天)
{
for (i=0;i<m;i++)//行
{
if (A[i][j]!=0)
{
A[i+m][j]=A[i][j]+m;
}
else //特殊處理：兩個隊各有一名選手有空，安排他們比賽
{
A[i+m][j] = i+1;
A[i][j] = i+m+1;
}
}
}
///////////安排兩組選手之間的比賽(後m-1天)////////////////////////
for(i=0,j=m+1;j<2*m;j++)
{
A[i][j] = j+1; //2. 1號選手的後m-1天比賽
A[ (A[i][j] -1) ][j] = i+1; //3. 他的對手後m-1天的安排
}
//以下的取值要依賴於1號選手的安排，所以之前先安排1號的賽程
for (i=1;i<m;i++) //第1組的其他選手的後m-1天的安排
{
for (j=m+1;j<2*m;j++)
{//2. 觀察得到的規則一：向下m+1~2*m循環遞增
A[i][j] = ((A[i-1][j]+1)%m==0)?A[i-1][j]+1 :m + (A[i-1][j]+1)%m;
//3. 對應第2組的對手也要做相應的安排
A[ (A[i][j]-1) ][j] = i+1;
}
}
return;
}
/*make:當前有m位（偶數）選手，分成兩組，每組由m/2位選手構成
由第一組的m/2位選手的安排來構成第二組的比賽安排，第一
組與第二組的比賽安排。要區分m/2為奇數和偶數兩種情況
*/
void make(int m)
{
if (isodd(m/2)) //m/2為奇數
odd(m/2);
else //m/2為偶數
even(m/2);
}
void tournament(int m)
{
if(m==1)
{
A[0][0]=1;
return ;
}
else if(isodd(m)) //如果m為奇數，則m+1是偶數
{
tournament(m+1); //按照偶數個選手來求解
replaceVirtual(m+1); //然後把第m+1號虛選手置成0
return ;
}
else //m是偶數，
{
tournament(m/2); //則先安排第1組的m/2人比賽
make(m); //然後根據演算法，構造左下、右下、右上、右下的矩陣
}
return ;
}
/*endprogram:回收分配的內存*/
void endprogram()
{
free(schele);
free(A);
}
int main()
{
init(); //初始化
tournament(N);//求解
print(); //列印結果
endprogram(); //回收內存
return 0;
}
『陸』 求助：循環賽—java源代碼
以前的！
====代碼====
package com;
import java.awt.BorderLayout;
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.List;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JList;
import javax.swing.JPanel;
import javax.swing.JTextField;
/**
* 網球賽
* @author Cris
* @ClassName: Match
* @Version
* @ModifiedBy
* @Copyright @ 2010 H&L Technology Inc.
* @date 2011-5-24 上午11:29:39
* @description
*/
public class Match implements ActionListener{
private JFrame f;
private JTextField tf;
private JPanel container;
private JList myList ;
private JLabel message;
private JButton b;
/**
* @author Cris
* @title: main
* @date 2011-5-23 上午11:07:27
* @param args void
*/
public static void main(String[] args) {
Match t = new Match();
t.go();
}
public void go(){
f = new JFrame("比賽");
f.setLocation(100, 200);
f.setSize(600,500);
container = new JPanel(new BorderLayout());
f.setContentPane(container);
JPanel title = new JPanel(new FlowLayout());
tf = new JTextField(10);
title.add(tf);
b = new JButton("確定");
b.addActionListener(this);
title.add(b);
message = new JLabel();
title.add(message);
container.add(title,BorderLayout.NORTH);
myList = new JList();
container.add(myList,BorderLayout.CENTER);
f.setVisible(true);
}
/**
* 顯示比賽結果
* @author Cris
* @title: show
* @date 2011-5-24 上午11:31:05
* @param n void
*/
private void show(int n){
Cris c = new Cris(n);
List<List<String[]>> result = c.getResult();
String[] str = new String[result.size()];
for (int i = 0; i < result.size(); i++) {
StringBuilder sb = new StringBuilder();
sb.append("第").append(i+1).append("天: ");
List<String[]> matchList = result.get(i);
for(String[] match : matchList){
sb.append("[").append(match[0]).append("-").append(match[1]).append("] ");
}
str[i] = sb.toString();
}
myList.setListData(str);
message.setText("");
f.setVisible(true);
}
/**
* 清空數據
* @author Cris
* @title: clear
* @date 2011-5-24 上午11:30:36 void
*/
private void clear(){
String[] str = {""};
myList.setListData(str);
message.setText("");
}
public void actionPerformed(ActionEvent e) {
clear();
String s = tf.getText();
if (s == null || "".equals(s = s.trim()) ) {
message.setText("請輸入一個偶數");
}
try {
int n = Integer.parseInt(s);
if (n <= 0 || n % 2 != 0) {
message.setText("請輸入一個偶數");
}else{
show(n);
}
} catch (Exception ex) {
message.setText("請輸入一個偶數");
}
f.setVisible(true);
}
}
第二個類：
package com;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class Cris {
/**選手數量*/
private int n ;
/**各個運動員還沒進行的比賽 key:球員名稱，value:需進行的比賽集合*/
private Map<String, List<String[]>> playerMacth ;
/**球員人名*/
private String[] players ;
/**最終每天的比賽分布集合*/
private List<List<String[]>> result;
/**所有可選的比賽*/
private List<List<String[]>> allMatchData[];
/**每天的比賽*/
List<String[]> dayMatch ;
/**一個隨機對象*/
private Random r;
/**當前運算到的天數*/
private int nowDay;
public Cris(int n){
this.n = n;
playerMacth = new HashMap<String, List<String[]>>();;
result = new ArrayList<List<String[]>>();
allMatchData = new LinkedList[n-1];
r = new Random();
init();
go();
}
/**
* 初始化球員
* @author Cris
* @title: init
* @date 2011-5-23 下午04:22:32 void
*/
private void init(){
//定義球員人名，以數字代表，從1開始
players = new String[n];
for (int i = 0; i < players.length; i++) {
//定義球員的名字
players[i] = String.valueOf(i+1);
//存放每個球員要進行的比賽的集合
List<String[]> matchList = new LinkedList<String[]>();
//球員賽事集合
playerMacth.put(players[i], matchList);
//球員集合，不變
// playerListConst.add(players[i]);
}
//定義每個人的比賽
for (int i = 0; i < players.length -1; i++) {
for (int j = i+1; j < players.length ; j++) {
String[] match = {players[i],players[j]};//定義一個比賽
//把此賽事添加到相應球員需比賽集合中
playerMacth.get(players[i]).add(match);
playerMacth.get(players[j]).add(match);
}
}
}
/**
* 隨機獲得一個當前天數可進行的比賽組合,並把此比賽組合從總集合中移除
* 如果當前天數無比賽，則先獲得比賽，再隨機
* @author Cris
* @title: getNowDayMatch
* @date 2011-5-24 上午09:48:23
* @return List<String[]>
*/
private List<String[]> getNowDayMatch(){
if (allMatchData[nowDay] == null) {
setAllMatchNowDay();
}
if (! allMatchData[nowDay].isEmpty()) {
int index = r.nextInt(allMatchData[nowDay].size());
List<String[]> list = allMatchData[nowDay].get(index);
allMatchData[nowDay].remove(index);
return list;
}else {
return null;
}
}
/**
* 取消前一天的比賽
* @author Cris
* @title: cancelYesterday
* @date 2011-5-24 上午09:56:12 void
*/
private void cancelYesterday(){
//清空當前天數的可選比賽組合
allMatchData[nowDay] = null ;
//時間恢復到前一天
nowDay--;
//獲得前一天的比賽
List<String[]> matchList = result.get(nowDay);
//取消前一天的比賽
result.remove(nowDay);
//恢復每個運動員未進行的比賽
for(String[] match : matchList){
playerMacth.get(match[0]).add(match);
playerMacth.get(match[1]).add(match);
}
}
public void go(){
//循環比賽天數
for ( nowDay = 0; nowDay < n -1; ) {
//1.隨機一個比賽
List<String[]> matchList = getNowDayMatch();
//無比賽組合 ，返回上一天 取消上一天的比賽，時間回退到前一天,跳過此次循環
if (matchList == null) {
cancelYesterday();
continue;
}
//3遍歷比賽 去除運動員 去除運動員的未進行比賽
for(String[] match : matchList){
playerMacth.get(match[0]).remove(match);
playerMacth.get(match[1]).remove(match);
}
result.add(matchList);
nowDay++;
}
}
/**
* 從1號隊員開始，獲得當前天數所有可組合的賽事
* @author Cris
* @title: setAllMatchNowDay
* @date 2011-5-24 上午09:42:51 void
*/
private void setAllMatchNowDay(){
allMatchData[nowDay] = new LinkedList<List<String[]>>();
int n = 1;//1號運動員
//此運動員未進行的比賽
List<String[]> matchList = playerMacth.get(String.valueOf(n));
for(String[] match : matchList){
List<String[]> selectedList = new ArrayList<String[]>();
selectedList.add(match);
doDetAllMatchNowDay(n+1, selectedList);
}
}
/**
* 今天比賽的所有組合
* @author Cris
* @title: doDetAllMatchNowDay
* @date 2011-5-24 上午09:46:05
* @param playerNum
* @param selectedList void
*/
private void doDetAllMatchNowDay(int playerNum,List<String[]> selectedList){
//運動員名稱
String player = String.valueOf(playerNum);
boolean flag = true;
//判斷此運動員是不是已被選過
for(String[] match : selectedList){
if (match[0].equals(player) || match[1].equals(player)) {
flag = false;
break;
}
}
//已被選過
if ( flag == false) {
//最後一個人員
if (playerNum == n) {
allMatchData[nowDay].add(selectedList);
}else{
doDetAllMatchNowDay(playerNum+1, selectedList);
}
return;
}
//此運動員未進行的比賽
List<String[]> matchList = playerMacth.get(player);
//此運動員可選擇的比賽
List<String[]> canDoList = new ArrayList<String[]>();
for(String[] match : matchList){
flag = true;
for(String[] selected : selectedList){
if(match[0].equals(player)){
if(match[1].equals(selected[0])){
flag = false;
}else if(match[1].equals(selected[1])){
flag = false;
}
}else{
if(match[0].equals(selected[0])){
flag = false;
}else if(match[0].equals(selected[1])){
flag = false;
}
}
}
if (flag) {
canDoList.add(match);
}
}
//遍歷此運動員可選擇的比賽
for(String[] match : canDoList){
List<String[]> newList = ArrayList(selectedList);
//記錄當前比賽
newList.add(match);
//最後一個人員
if (playerNum == n) {
allMatchData[nowDay].add(newList);
}else{
doDetAllMatchNowDay(playerNum+1, newList);
}
}
}
/**
* 復制集合
* @author Cris
* @title: ArrayList
* @date 2011-5-24 上午09:24:44
* @param list
* @return List<String[]>
*/
private List<String[]> ArrayList(List<String[]> list){
List<String[]> newList = new ArrayList<String[]>();
for(String[] s : list){
newList.add(s);
}
return newList;
}
public List<List<String[]>> getResult() {
return result;
}
}