[분 치 법] 순환 경기 표

4133 단어 알고리즘
제목:
2k 명의 선수 가 테니스 순환 경 기 를 하고 경기 표를 디자인 하여
  • 한 선수 당 다른 n - 1 선수 와 한 번 씩
  • 선수 당 하루 에 한 번 만 경기 할 수 있다
  • 시리즈 가 n - 1 일 만 에 끝났다
    • 일정표 i 행 j 열 은 i 번 째 선수 가 j 일 에 만난 선 수 를 나타 낸다.
    분석:
    k = 3, n = 8 의 상황 을 고려 하여 분 치 사상 을 이용 하여 모든 선 수 를 끊임없이 두 조로 나 누 어 최종 적 으로 두 사람 만 남아 경 기 를 하 는 것 으로 전환 시 킨 다음 에 두 사람의 경기 배정 에 따라 전체 경기 표를 얻 을 수 있다.
  • 먼저 경기 할 8 명의 선수 for(int i = 1; i <= 8; i++) a[1][i] = i;
    • 를 나열 한다.
  • 표 앞의 두 줄 을 고려 하여 두 사람 이 한 조로 나 누 어 표를 n / 2 조각 으로 나 누고 각 조각의 왼쪽 상단 요 소 를 오른쪽 아래 에 베 끼 고 오른쪽 상단 요 소 를 왼쪽 아래 에 베 꼈 다
    • .
  • 앞의 네 줄 을 계속 고려 하고 네 사람 이 한 조로 나 누 어 표를 n / 4 조각 으로 나 누 었 다. 마찬가지 로 각 조각의 왼쪽 상단 요 소 를 오른쪽 아래 에, 오른쪽 상단 요 소 를 왼쪽 아래 에 베 꼈 다
    • .
  • 마지막 으로 앞의 8 행, 8 명 을 한 조로 고려 하여 표를 하나의 전체 로 보고 왼쪽 상단 의 요 소 를 오른쪽 아래 에 베 끼 고 오른쪽 상단 요 소 를 왼쪽 아래 에 베 꼈 다
    • .
  • 최종 획득 일정표
    • 1
    2
    3
    4
    5
    6
    7
    8
    2
    1
    4
    3
    6
    5
    8
    7
    3
    4
    1
    2
    7
    8
    5
    6
    4
    3
    2
    1
    8
    7
    6
    5
    5
    6
    7
    8
    1
    2
    3
    4
    6
    5
    8
    7
    2
    1
    4
    3
    7
    8
    5
    6
    3
    4
    1
    2
    8
    7
    6
    5
    4
    3
    2
    1
    코드:
    #include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int maxn = 10005;
int a[maxn][maxn];
int main (void)
{
    int k, m = 1;
    cin>>k;
    int t = pow(2,k);
    int n = t;

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

    //    ，               ，        
    for(int i = 1; i <= k; i++){
        n /= 2;
        for(int p = 1; p <= n; p++){
            for(int j = 1; j <= m; j++){
                for(int k = 1; k <= m; k++){
                    a[j+m][k+2*m*(p-1)] = a[j][m+k+2*m*(p-1)];
                    a[j+m][m+k+2*m*(p-1)] = a[j][k+2*m*(p-1)];
                }
            }
        }
        m *= 2;
    }

    //    
    for(int i = 1; i <= t; i++){
        for(int j = 1; j <= t; j++){
            cout<<a[i][j]<<' ';
        }
        cout<<endl;
    }
}
    SWEA1247. 최적경로
    정렬 기본 사상 직접 삽입

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage