//////////////////////////////////////////////////////////////////////////////
//
// 14. 有黑白棋子各有Ｎ个（分别用＊和Ｏ代替），按下图方式排列
//
//        ＊＊＊．．．＊＊＊ＯＯＯ．．．ＯＯＯ
//
//            Ｎ个黑棋            Ｎ个白棋
//
// 允许将相邻两个棋子互换位置，最后使队形成黑白交替排列，试编程实现该操作。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#define N  5
void main()
{
    char *str = new char[2*N], temp;
    int i, start, end;
    for(i = 0; i < N; i++)
        str[i] = '*';
    for(; i < 2*N; i++)
        str[i] = 'o';
    printf("%s\n", str);

    for(start = N-1, end = 2*N-2; start < end; start--,end-=2)
    {
        for(i = start; i < end; i++)
        {
            temp     = str[i];
            str[i]   = str[i+1];
            str[i+1] = temp;
            printf("%s\n",str);
        }
    }
    delete[] str;
}

//////////////////////////////////////////////////////////////////////////////
//
// 15. 已知６个城市，用ｃ[i,j]表示从ｉ城市到城市ｊ是否有单向的直达汽车
//
// （１=<ｉ〈＝６，１〈＝ｊ〈＝６）, c[i,j]=1 表示城市ｉ到城市ｊ有单向直达汽
// 车； 否则 ｃ[i,j]＝0.  试编制程序，对于给出的城市代号ｉ，打印出从该城市出
// 发乘车（包括转车）可以到达的所有城市。 
//////////////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <assert.h>
#define  N  6

int visited[N] = {0};

void visit(int c[][N], int i)
{
    if(!visited[i])
    {
        visited[i] = 1;
        for(int j = 0; j < N; j++)
            if(c[i][j] && !visited[j])
                visit(c, j);
    }
}

void main( void )
{
    int  c[N][N], i, j, n;
    
    srand((unsigned)time(NULL));
    for (i = 0; i < N; i++ )
    {
        for(j = 0; j < N; j++)
        {
            c[i][j] = rand()%2;
            printf( "%6d", c[i][j]);
        }
        putchar('\n');
    }

    scanf("%d", &n);
    assert(n < N);
    visit(c, n);
    for (i = 0; i < N; i++ )
    {
        if(visited[i])
            printf( "%6d", i);
    }
}

//////////////////////////////////////////////////////////////////////////////
//
// 17. 编写一个程序，当输入不超过６０个字符组成的英文文字时，计算机将这个句子
// 中的字母按英文字典字母顺序重新排列，排列后的单词的长度要与原始句子中的长度
// 相同。例如：
//
//    输入：
//
//    ＴＨＥ ＰＲＩＣＥ ＯＦＢＲＥＡＤ ＩＳ ￥１ ２５ ＰＥＲ ＰＯＵＮＤ
//
//    输出：
//
//    ＡＢＣ ＤＤＥＥＥ ＥＦＨＩＩＮＯ ＯＰ ￥１ ２５ ＰＰＲ ＲＲＳＴＵ
//
// 并且要求只对Ａ到Ｚ的字母重新排列，其它字符保持原来的状态。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "ctype.h"
#include "string.h"
#define  MAX  60

void main()
{
    char str[MAX+1]  = " THE PRICE OFBREAD IS $1 25 PER POUND", *p, *q, temp;     
    int len = strlen(str);
    for(p = str; p < str+len-1; p++)
    {
        for(q = p; q < str+len; q++)
        {
            if(!isalpha(*q))
                continue;
            if(*p > *q)
            {
                temp = *p;
                *p   = *q;
                *q   = temp;
            }
        }
    }
    printf("%s\n", str);
}

//////////////////////////////////////////////////////////////////////////////
//
// 18. 在一线性七个格位置的图上有两种不同颜色的棋子Ａ，Ｂ. 排列如下图所示，中间
// 格的位置为空。
//          ┎─┰─┰─┰─┰─┰─┰─┒
//          ┃Ａ┃Ａ┃Ａ┃  ┃Ｂ┃Ｂ┃Ｂ┃
//          ┖─┸─┸─┸─┸─┸─┸─┚
// 要求将Ａ，Ｂ的现行位置交换,形成下图中的排列：
//          ┎─┰─┰─┰─┰─┰─┰─┒
//          ┃Ｂ┃Ｂ┃Ｂ┃  ┃Ａ┃Ａ┃Ａ┃
//          ┖─┸─┸─┸─┸─┸─┸─┚
// 移动棋子的条件：
//   (1) 每个格中只准放一个棋子。
//   (2) 任意一个棋子均可移动一格放入空格内。
//   (3) 一方的棋子均可跳过另一方的一个棋子进入空格。
//   (4) 任何棋子不得跳跃两个或两个以上棋子（无论颜色同异）
//   (5) 任何一个颜色棋子只能向前跳，不准向后跳。
// 编程完成有关的移动，并且完成具有２Ｎ＋１个格子的情形. 其中两种颜色各有
// Ｎ个棋子,且中间为空格.
//////////////////////////////////////////////////////////////////////////////[color=FF0000][size=3]程序错误，参见第八十四楼zy1121的代码[/size][/color]
#include "stdio.h"
#define  N  7

void swapc(int a, int b, char *str)
{
    char temp = str[a];
    str[a] = str[b];
    str[b] = temp;
    printf("%s\n", str);
}
void main()
{
    int i ,j, end = 0;
    char str[N+1];
    for(i = 0; i < N/2; i++)
        str[i] = 'A';
    str[i++] = 'O';
    for(; i < N; i++)
        str[i] = 'B';
    str[N] = 0;
    printf("%s\n", str);
    for(i = N/2; i < N-1; i++)
        swapc(i, i+1, str);
    for(i = N/2; i < N-1; i++)
    {
        for(j = i; j > end; j--)
            swapc(j, j-1, str);
        end++;
    }
    for(i = N-2; i >= N/2; i--)
        swapc(i, i+1, str);
}

//////////////////////////////////////////////////////////////////////////////
//
// 20. (Ｎ皇后) 在国际象棋的棋盘上放置Ｎ个皇后，使其不能互相攻击，即任意
// 两个皇后不能处在棋盘的同一行，同一列，同一斜线上，试问共有多少种摆法？ 
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "conio.h"
#define N 8

static int a[N][N], count;
bool legal(int row, int col)
{
    int i, j;
    for(i = 0; i < row; i++)
        if(a[i][col])
            return false;
    for(j = 0; j < col; j++)
        if(a[row][j])
            return false;
    for(i = row-1, j = col-1; (i>=0) &&(j>=0); i--, j--)
        if(a[i][j])
            return false;
    for(i = row-1, j = col+1; (i>=0) &&(j<N); i--, j++)
        if(a[i][j])
            return false;
    return true;
}

void trial(int row)
{
    int p, col;
    if(row == N)
    {
        ++count;
        printf("********%d*********\n", count);
        for(p = 0; p < N; p++)
        {
            for(col = 0; col < N; col++)
                printf("%4d", a[p][col]);
            printf("\n");
        }
    }
    else
    {
        for(col = 0; col < N; col++)
        {
            a[row][col] = 1;
            if(legal(row, col))
                trial(row+1);
            a[row][col] = 0;
        }
    }
}

void main()
{    
    trial(0);
}


#include "stdio.h"
#include "conio.h"
#define N 8

static int a[N][N], count, row;
bool legal(int row, int col)
{
    int i, j;
    for(i = 0; i < row; i++)
        if(a[i][col])
            return false;
    for(j = 0; j < col; j++)
        if(a[row][j])
            return false;
    for(i = row-1, j = col-1; (i>=0) &&(j>=0); i--, j--)
        if(a[i][j])
            return false;
    for(i = row-1, j = col+1; (i>=0) &&(j<N); i--, j++)
        if(a[i][j])
            return false;
    return true;
}

void main(int row)
{
    printf("\n%4d\n", row);
    int p, col;
    if(row == N+1)
    {
        ++count;
        printf("********%d*********\n", count);
        for(p = 1; p <= N; p++)
        {
            for(col = 0; col < N; col++)
                printf("%4d", a[p][col]);
            printf("\n");
        }
        _getch();
    }
    else
    {
        for(int col = 0; col < N; col++)
        {
            a[row][col] = 1;
            if(legal(row, col))
                main(row+1);
            a[row][col] = 0;
        }
    }
}

//////////////////////////////////////////////////////////////////////////////
//
//21. 请设计一个程序，由计算机把１..￣.８的八个自然数填入图中，使得横、
// 竖、对角任何两个相邻的小方格中的两个数是不连续的。(下图右侧的 4 个图
// 为禁止的情形).
//
//            ┌─┐          ┌─┐               ┌─┐
//            │  │          │４│               │８│
//        ┌─┼─┼─┐      └─┼─┐       ┌─┼─┘
//        │  │  │  │          │５│       │７│
//        ├─┼─┼─┤          └─┘       └─┘
//        │  │  │  │      ┌─┐
//        └─┼─┼─┘      │６│           ┌─┬─┐
//            │  │          ├─┤           │１│２│
//            └─┘          │７│           └─┴─┘
//                            └─┘
///////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "string.h"
#include "math.h"
int a[4][3];
int count = 0;
bool legalelem(int row, int col)
{
    switch (row)
    {
    case 0:
    case 3:
        if(col == 1)
            return true;
        else
            return false;
    case 1:
    default:
        return true;
    }
}

bool islegal(int row, int col)
{
    int i, j;
    for(i = row-1; i <= row+1; i++)
    {
        if(i < 0 || i > 3)
            continue;
        for(j = col-1; j <= col+1; j++)
        {
            if(j < 0 || j > 2)
                continue;
            if(abs(a[i][j] - a[row][col]) == 1)
                return false;
        }
    }
    return true;
}

void trace(int n)
{
    int i, j;
    if(n > 8)
    {
        ++count;
        printf("\n********** %d **********\n", count);
        for(i = 0; i < 4; i++)
        {
            for(j = 0; j < 3; j++)
            {
                if(legalelem(i, j))
                    printf("%6d", a[i][j]);
                else
                    printf("%*s", 6, "");
            }
            putchar(10);
        }
        return;
    }
    for(i = 0; i < 4; i++)
    {
        for(j = 0; j < 3; j++)
        {
            if(a[i][j] == -1 && legalelem(i, j))
            {
                a[i][j] = n;
                if(islegal(i, j))
                    trace(n+1);
                a[i][j] = -1;
            }                
        }
    }        
}

void main()
{
    int i, j;
    for(i = 0; i < 4; i++)
        for(j = 0; j < 3; j++)
            a[i][j] = -1;
    trace(1);
}

///////////////////////////////////////////////////////////////////////////
// 22. 在一个４＊４的小方格（如图所示）中放置８个＊号，使得每行每列放且
// 仅放两个＊号。
//          ┌─┬─┬─┬─┐
//          │＊│＊│  │  │
//          ├─┼─┼─┼─┤
//          │＊│  │＊│  │
//          ├─┼─┼─┼─┤
//          │  │＊│  │＊│
//          ├─┼─┼─┼─┤
//          │  │  │＊│＊│
//          └─┴─┴─┴─┘
//
// 求出所有的基本解。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#define N 4

static int a[N][N], count;

bool legal(int row, int col)
{
    int sum, p;
    for(sum = 0, p = 0; p < row; p++)
        sum += a[p][col];
    if(sum < 2)
    {
        for(sum = 0, p = 0; p < col; p++)
            sum += a[row][p];
        if(sum < 2)
            return true;
        else
            return false;
    }
    else
        return false;
}

void trial(int row)
{
    if(row == N)
    {
        ++count;
        printf("******** %d ********\n", count);
        for(int p = 0; p < N; p++)
        {
            for(int q = 0; q < N; q++)
                printf("%4d", a[p][q]);
            printf("\n");
        }
    }
    else
    {
        for(int j1 = 0; j1 < N-1; j1++)
        {
            a[row][j1] = 1;
            if(legal(row, j1))
            {
                for(int j2 = j1+1; j2 < N; j2++)
                {
                    if(!a[row][j2])
                    {
                        a[row][j2] = 1;
                        if(legal(row, j2))
                            trial(row+1);
                        a[row][j2] = 0;
                    }
                }
            }
            a[row][j1] = 0;
        }
    }
}

void main()
{
    trial(0);
}

//////////////////////////////////////////////////////////////////////////////
//
// 24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班，
// 向东要走Ｍ块，向北要走Ｎ块，（见图）。请设计一个程序，由计算机寻找并
// 打印出所有的上班的路径。（只能向右或向上,否则会死循环）
//
//                                               单位
//
//           ┬   ┌─┬─┬─┬─┬─┬─┬─┐
//           │   │  │  │  │  │  │  │  │
//           │   ├─┼─┼─┼─┼─┼─┼─┤
//           ↓   │  │  │  │  │  │  │  │
//           Ｎ   ├─┼─┼─┼─┼─┼─┼─┤
//           ↑   │  │  │  │  │  │  │  │
//           │   ├─┼─┼─┼─┼─┼─┼─┤
//           │   │  │  │  │  │  │  │  │
//           ┴   └─┴─┴─┴─┴─┴─┴─┘
//           家   ├─────→Ｍ←─────┤
//////////////////////////////////////////////////////////////////////////////
//只能向右或向上,否则会死循环
#include "stdio.h"
#define  M  6
#define  N  5

typedef struct
{
    int i;
    int j;
}postype;

void trial(postype path[], int i)
{
    if(path[i].i > N || path[i].j > M)
        return;
    if(path[i].i == N && path[i].j == M)
    {
        printf("\n\n");
        for(int j = 0; j <= i; j++)
            printf("<%d, %d>\t", path[j].i, path[j].j);
    }
    else
    {
        path[i+1].i = path[i].i+1;
        path[i+1].j = path[i].j;
        trial(path, i+1);
        path[i+1].i = path[i].i;
        path[i+1].j = path[i].j+1;
        trial(path, i+1);
    }
}

void main()
{
    postype path[50];
    path[0].i = path[0].j = 0;
    trial(path, 0);
}

//////////////////////////////////////////////////////////////////////////////
//
//36. 猴子选大王：
//   ① N 只猴子站成一行，每 M 只报数。先从头到尾，报到尾后，再返回从尾到头
// 报数，打印每次方向及过程，直到剩下二只时，以排到后面的(指报数方向)为大王。 
//   ② N 只猴子围成一圈，从第 P 个开始，每隔 M 只报数，打印每次过程，只剩下
// 一个时为大王。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "malloc.h"
#define  N   20
#define  M   3
#define  RUN 1 //RUN == 0 execute 2   RUN == 1 execute 1

#if RUN
typedef struct node{
    int no;
    node* next;
    node* front;
}node;

node* create(){
    node *p, *q, *head;
    printf("\nThe Original Monkey Link Is:\n");
    p = head = (node *)malloc(sizeof(node));
    p->front = NULL;
    for(int i = 1;i <= N; i++){
        p->no = i;
        p->next = (node *)malloc(sizeof(node));
        printf("%d\t", p->no);
        q = p;
        p = p->next;
        p->front = q;
    }
    free(p);
    q->next = NULL;
    return head;
}

void kickout(node *head){
    node *p = head;
    bool di = true;
    printf("\nThe Sequence Of Monkey Wash Out Is:\n");
    for(int i = 1; p->front != p->next; i++){
        if(di){
            if(!(i%M)){
                p->front->next = p->next;
                printf("%d\t", p->no);
                if(p->next)
                    p->next->front = p->front;        
            }
            if(p->next)
                p  = p->next;
            else{
                p  = p->front;
                di = false;
            }
        }
        else{
            if(!(i%M)){
                p->next->front = p->front;
                printf("%d\t", p->no);
                if(p->front)
                    p->front->next = p->next;        
            }
            if(p->front)
                p = p->front;
            else{
                p  = p->next;
                di = true;
            }
        }
    }
    printf("\nThe Winner Is %d.Congratulation!\n", p->no);
}

#else
typedef struct node{
    int no;
    node* next;
}node;

//////////////////////////////////////////////////////////////////////////////
//
// 38. 有一集合中有 N 个元素，每个元素均为自然数。给定一个 total （假设每个
// 元素值均小于total)，求满足条件的所有子集，子集中各元素之和应等于total。
//////////////////////////////////////////////////////////////////////////////
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"

int a[] = {1, 2, 3, 4, 7, 10};
const int N = sizeof(a)/sizeof(int);

char print[30], temp[5];
void trace(int i,int j, int a[], int b[], int total)
{
    if(i == N) //not "i > N"
    {
        int sum = 0, p;
        for(p = 0; p < i-1; p++)
            sum += b[p];
        if(sum == total)
        {
            memset(print, 0, sizeof(print));
            strcat(strcat(print, itoa(total, temp, 10)), "= ");
            for(p = 0; p < i-1; p++)
            {
                if(b[p])
                    strcat(strcat(print, itoa(b[p], temp, 10)), " +");
            }
            memset(print+strlen(print)-1, 0, 2);
            printf("%s\n", print);
        }

    }
    else
    {
        b[j] = a[i];
        trace(i+1, j+1, a, b, total);
        b[j] = 0;
        trace(i+1, j, a, b, total); //not "trace(i+1, j+1, a, b, total);"
    }
}
void main()
{
    int *b = new int[N], total;
    memset(b, 0, sizeof(a));
    printf("a[%d] = {", N);
    for(int i = 0; i < N; i++)
        printf(" %d,", a[i]);
    printf("}\ninput the total, insure its value larger than each element of array a:");
    scanf("%d", &total);
    trace(0, 0, a, b, total);
}

//////////////////////////////////////////////////////////////////////////////
//
// 39. a: 一个集合满足如下条件：
//         (1) 1是集合的元素；
//         (2) 若 P 是集合的元素，则 2*P+1，4*P+5 也是集合的元素。
//         求：此集合中最小的 K 个元素。
//
//     b: 对ＡＢＣ作全排列而得的六个三位数之和为 2886。
/////////////////////////////////////////////////////////////////////////////
///垃圾贴
// a:
#include "stdio.h"
#include "malloc.h"
#define MAX_LEN  1000
#define RUN  0

#if RUN
unsigned int a[MAX_LEN];
void CreateArray(int p, int j)
{    
    if(j < MAX_LEN)
    {
        a[j++] = a[p]*2+1;
        a[j++] = a[p]*4+5;
        CreateArray(p+1, j);            
    }
}

void sort(unsigned int k)
{
    unsigned int i, j, min;
    for(i = 0; i < k; i++)
    {
        min = a[i];
        for(j = i+1; j < MAX_LEN; j++)
            if(a[j] < min)
            {
                min  = a[j];
                a[j] = a[i];
                a[i] = min;
            }
        printf("%d\t", a[i]);
    }
}

void main()
{
    unsigned int i, k;
    a[0]= 1;
    CreateArray(0, 1);
    for(i = 0; i < MAX_LEN; i++)
        printf("%d\t", a[i]);
    printf("\ninput k:");
    scanf("%d", &k);
    sort(k);
}

#else
// b.
void main()
{
    int i, j, k;
    for(i = 1; i < 10; i++)
        for(j = 1; j < 10; j++)
            for(k = 1; k < 10; k++)
                if(i+j+k == 13)
                    printf("%5d %5d %5d\n", i, j, k);
}
#endif

//////////////////////////////////////////////////////////////////////////////
//
// 40. 一个整型变量只能用来存贮较小的 N！的值，当 N 较大时，可将阶乘值中的
// 每一个数字放在一个一维数组的一个元素中。使用这方法，打印：
//    ① Ｎ！的值；
//    ② Ｎ！－Ｍ！（Ｍ＞Ｎ）；
//    ③ Ｎ！＋Ｍ！ 
////////////////////////////////////////////////////////////////////////////// 
#include "stdio.h"
#include "stdlib.h"
#include "assert.h"
#include "time.h"
#define MAX_LEN  100000

int menu()
{
    int choose;
    printf("\t\t***********************************************\n");
    printf("\t\t*                                             *\n");
    printf("\t\t*             Calculate Aout N!               *\n");
    printf("\t\t*                                             *\n");
    printf("\t\t***********************************************\n\n");
    printf("\t\t1. Calculate N!\n\n");
    printf("\t\t2. Calculate M!-N!\n\n");
    printf("\t\t3. Calculate M!+N!\n\n");
    printf("\t\tSelect the option which you wanna operate:");
    while(scanf("%d", &choose), (choose < 1 || choose > 3))
        printf("\t\tInput error, select again:");
    system("cls");
    return choose;
}

void print(int a[], int end)
{
    for(int i = end-1; i >= 0; i--)
        printf("%d", a[i]);
    printf("\n\n");
}

void factorial(int n, int pro[], int &end)
{
    clock_t starttime = clock();
    int i, j, k = 1, c, temp;
    pro[0] = 1;
    for(i = 1; i <= n; i++)
    {
        c = 0;
        for(j = 0; j < k; j++)
        {
            temp   = pro[j]*i + c;
            pro[j] = temp%10;
            c      = temp/10;
        }
        while(c)
        {
            pro[j++] = c%10;
            c /= 10;
        }
        k = j;
    }
    clock_t endtime = clock();
    printf("\nExecute this program costs %g seconds\n", 
        (double)(endtime - starttime)/CLOCKS_PER_SEC);
    end = k;
    printf("%d! = ", n);
    print(pro, end);
}

void add(int a[], int b[], int endm, int endn)
{
    int i, end = (endm > endn)?endm:endn;
    for(i = 0; i < end; i++)
    {
        a[i] += b[i];
        if(a[i] > 9)
        {
            a[i] %= 10;
            a[i+1]++;
        }
    }
    print(a, end);
}

void sub(int a[], int b[], int endm, int endn)
{
    int i, end = (endm > endn)?endm:endn;
    for(i = 0; i < end; i++)
    {
        a[i] -= b[i];
        if(a[i] < 0)
        {
            a[i] += 10;
            a[i+1]--;
        }
    }
    print(a, end);
}

void main()
{
    int a[MAX_LEN] = {0}, b[MAX_LEN] = {0};
    int m, n, endm, endn;
    switch (menu())
    {
    case 1:
        printf("Please input the value of N:");
        scanf("%d", &n);
        factorial(n, a, endn);
        break;
    case 2:        
        printf("Please input the value of M and N(M >= N):");
        scanf("%d %d", &m, &n);
        assert(m >= n);
        factorial(m, a, endm);
        factorial(n, b, endn);
        printf("%d!-%d! = ", m, n);
        sub(a, b, endm, endn);
        break;
    default:
        printf("Please input the value of M and N:");
        scanf("%d %d", &m, &n);
        factorial(m, a, endm);
        factorial(n, b, endn);
        printf("%d!+%d! = ", m, n);
        add(a, b, endm, endn);
    }
}