main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

/*************************************************************************************
18. 在一线性七个格位置的图上有两种不同颜色的棋子Ａ，Ｂ. 排列如下图所示，中间
 格的位置为空。

          ┎─┰─┰─┰─┰─┰─┰─┒
          ┃Ａ┃Ａ┃Ａ┃  ┃Ｂ┃Ｂ┃Ｂ┃
          ┖─┸─┸─┸─┸─┸─┸─┚

 要求将Ａ，Ｂ的现行位置交换,形成下图中的排列：

          ┎─┰─┰─┰─┰─┰─┰─┒
          ┃Ｂ┃Ｂ┃Ｂ┃  ┃Ａ┃Ａ┃Ａ┃
          ┖─┸─┸─┸─┸─┸─┸─┚

 移动棋子的条件：

   (1) 每个格中只准放一个棋子。
   (2) 任意一个棋子均可移动一格放入空格内。
   (3) 一方的棋子均可跳过另一方的一个棋子进入空格。
   (4) 任何棋子不得跳跃两个或两个以上棋子（无论颜色同异）
   (5) 任何一个颜色棋子只能向前跳，不准向后跳。

 编程完成有关的移动，并且完成具有２Ｎ＋１个格子的情形. 其中两种颜色各有
 Ｎ个棋子,且中间为空格.

  分析: 列出最简单的几种(如N=3,N=5,N=7)的走法,总结规律
**************************************************************************************/

#include <stdio.h>
#include <malloc.h>

int count = 0;

//flag = 1,空格向右移动,否则向左移动
void move(char* chesses, int* ppos, int flag)
{
	if(flag)
	{ 
		chesses[*ppos] = chesses[*ppos+1];
		chesses[*ppos+1] = ' ';
		*ppos = *ppos+1;
	}
	else
	{
		chesses[*ppos] = chesses[*ppos-1];
		chesses[*ppos-1] = ' ';
		*ppos = *ppos-1;
	}
	count ++;
}

//flag = 1,空格向右跳,否则向左跳
void jump(char* chesses, int* ppos, int flag)
{
	
	if(flag)
	{ 
		chesses[*ppos] = chesses[*ppos+2];
		chesses[*ppos+2] = ' ';
		*ppos = *ppos + 2;
	}
	else
	{
		chesses[*ppos] = chesses[*ppos-2];
		chesses[*ppos-2] = ' ';
		*ppos = *ppos - 2;
	}
	count ++;
}

//显示棋子状态
void print_chesses(char* chesses,int size)
{
	int i;
	for(i=0; i<size; i++)
		printf("%c",chesses[i]);
	printf("\n");
}

void main()
{
	
	int n;
	int N;
	int pos;
	char* chesses;
	int count_jmp = 1;
	int move_dirt = 0;
	int jump_dirt = 1;
	int dc = 1;//计数递增方向,取-1和-1


	printf("请输入一个正整数n: ");
	scanf("%d", &n);

	N = 2*n + 1;
	pos = n;
	chesses = (char*)malloc(N*sizeof(char));

	{
		int i;
		for(i=0; i<n; i++)
			chesses[i] = 'A';
		chesses[i++] = ' ';
		for(;i<N; i++)
			chesses[i] = 'B';
		print_chesses(chesses,N);
	}

	while(count_jmp!=0)
	{
		int i;

		move(chesses, &pos, move_dirt);
		print_chesses(chesses,N);

		for(i=0; i<count_jmp; i++)
		{
			jump(chesses,&pos,jump_dirt);
			print_chesses(chesses,N);
		}
		jump_dirt = !jump_dirt;
		if(count_jmp == n)
		{
			dc = -dc;
		}
		else move_dirt = !move_dirt;;
		count_jmp += dc;
	}
	move(chesses, &pos, move_dirt);
	print_chesses(chesses,N);

	printf("%d\n",count+1);

	free(chesses);
}