一 : 组合算法 C++高效实现 (二进制辅助法)
1.什么是数学中的组合？
和排列不同的是，在组合中取出元素的顺序则不在考虑之中。从个元素中取出个元素，这个元素可能出现的组合数的总数量为：
以1,2,3,4,5中选2个数为例，总共的组合为：
1,2
1,3
1,4
1,5
2,3
2,4
2,5
3,4
3,5
4,5
2.在计算机中如何高效的实现排列算法？
乍一看，这个问题并不简单。有递归的实现方式，效率较低，还比较难，先不考虑。我们注意到一种以二进制的思想的实现方式，比较高效，来讲讲它。
（www.61k.com)首先还是需要讲下上次的排列算法中比较高效的实现方式（），就是把1,2,3的全排列，换算成求一个三位数，由1,2,3组成，从小到大所有的可能性。
123 < 132 < 213 < 231 < 312 < 321
我们还是以1,2,3,4,5中选2个数为例。
我们这次的排列非常的像，我们用一个五个数的数组表示一个5位数的二进制数字，(其中1表示选中该数字，0则不是)这样用一个二进制数来表示一个排列。如果这个二进制遍历所有的可能性(0~31)，且只有两个1组成的话，就是一个我们想要的排列结果。这里我们换成十进制从左往右换算，发现刚好是从小到大。
1,2 (1,1,0,0,0) -- 3(十进制)
1,3 (1,0,1,0,0) -- 5
2,3 (0,1,1,0,0) -- 6
1,4 (1,0,0,1,0) -- 9
2,4 (0,1,0,1,0) -- 10
3,4 (0,0,1,1,0) -- 12
1,5 (1,0,0,0,1) -- 17
2,5 (0,1,0,0,1) -- 18
3,5 (0,0,1,0,1) -- 20
4,5 (0,0,0,1,1) -- 24
如何用代码实现呢？
需要用以下策略：
1.m 选 n， 初始化m个数，它们都是0，前n个都变成1，表示最小的二进制。
2.如何找到下一个较大的数呢？因为我们这里的二进制是从左往右，所以，当发现一个1,0时，我们把它改成0,1的时候，这个数就变大了！
3.根据策略2的话(0,1,1,0,0)--6下一个二进制数应该是(0,1,0,1,0)--10，但是比(0,1,1,0,0)要大的下一个数应该是(1,0,0,1,0)--9。所以
我们要把1,0换成0,1的时候，还要把0,1中0的前面所有1都移到最前面，这样才是最小的数，大家理解下这句。因为我们的二进制是从左往右的。
代码如下，非常简短。
// MyCombination.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printResult(vector<int>& vecInt, int t[]){
for(int i = 0; i < vecInt.size(); ++i){
if(vecInt[i] == 1){
cout << t[i] << " ";
}
}
cout << endl;
}
bool compare(int a, int b){
if(a > b){
return true;
}else{
return false;
}
}
void combination(int t[], int c, int total){
//initial first combination like:1,1,0,0,0
vector<int> vecInt(total,0);
for(int i = 0; i < c; ++i){
vecInt[i] = 1;
}
printResult(vecInt, t);
for(int i = 0; i < total - 1; ++i){
if(vecInt[i] == 1 && vecInt[i+1] == 0){
//1. first exchange 1 and 0 to 0 1
swap(vecInt[i], vecInt[i+1]);
//2.move all 1 before vecInt[i] to left
sort(vecInt.begin(),vecInt.begin() + i, compare);
//after step 1 and 2, a new combination is exist
printResult(vecInt, t);
//try do step 1 and 2 from front
i = -1;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int N = 5;
int t[N] = {1, 2, 3, 4, 5};
combination(t, 2, N);
system("pause");
return 0;
}
3.如何求所有的组合呢？
如果你理解了上面的东西，我们再来思考一个简单的问题，如何求1,2,3 的所有组合结果：
别害怕，这个问题比上面的还要简单，也是二进制的思想，我们用一个3位的二进制来表示一个结果，刚好是从0~7
{} 000
1 001
2 010
1,2 011
3 &“犇嫑”nbsp;100
2,3 110
1,2,3 111
代码如下(位运算不懂的话，看这篇文章《来谈谈C++ 位运算 & | << >> ^ ~ %》)：
// MyCombination.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printEachResult(int t[], int index, int total){
for(int i = 0; i < total; ++i){
if((index>>i)&1 == 1){
cout << t[i] << " ";
}
}
cout << endl;
}
void combination(int t[],int count){
for(int i = 0; i < (1<<count); ++i){
printEachResult(t, i, count);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
const int N = 3;
int t[N] = {1, 2, 3};
combination(t,N);
system("pause");
return 0;
}
二 : C语言如何实现五子棋游戏
五子棋游戏是一款很经典的智力游戏，只有学过编程语言的人，把五子棋的编程原理弄懂了，就能用自己熟悉的语言实现出来，在这里给大家分享，c语言五子棋源码，仅供大家参考借鉴。（www.61k.com)
#include <stdio.h>
#include <bios.h>
#include <ctype.h>
#include <conio.h>
#include <dos.h>
#define CROSSRU 0xbf /*右上角点*/
#define CROSSLU 0xda /*左上角点*/
#define CROSSLD 0xc0 /*左下角点*/
#define CROSSRD 0xd9 /*右下角点*/
#define CROSSL 0xc3 /*左边*/
#define CROSSR 0xb4 /*右边*/
#define CROSSU 0xc2 /*上边*/
#define CROSSD 0xc1 /*下边*/
#define CROSS 0xc5 /*十字交叉点*/
/*定义棋盘左上角点在屏幕上的位置*/
#define MAPXOFT 5
#define MAPYOFT 2
/*定义1号玩家的操作键键码*/
#define PLAY1UP 0x1157/*上移--'W'*/
#define PLAY1DOWN 0x1f53/*下移--'S'*/
#define PLAY1LEFT 0x1e41/*左移--'A'*/
#define PLAY1RIGHT 0x2044/*右移--'D'*/
#define PLAY1DO 0x3920/*落子--空格键*/
/*定义2号玩家的操作键键码*/
#define PLAY2UP 0x4800/*上移--方向键up*/
#define PLAY2DOWN 0x5000/*下移--方向键down*/
#define PLAY2LEFT 0x4b00/*左移--方向键left*/
#define PLAY2RIGHT 0x4d00/*右移--方向键right*/
#define PLAY2DO 0x1c0d/*落子--回车键Enter*/
/*若想在游戏中途退出, 可按 Esc 键*/
#define ESCAPE 0x011b
/*定义棋盘上交叉点的状态, 即该点有无棋子 */
/*若有棋子, 还应能指出是哪个玩家的棋子 */
#define CHESSNULL 0 /*没有棋子*/
#define CHESS1 'O'/*一号玩家的棋子*/
#define CHESS2 'X'/*二号玩家的棋子*/
/*定义按键类别*/
#define KEYEXIT 0/*退出键*/
#define KEYFALLCHESS 1/*落子键*/
#define KEYMOVECURSOR 2/*光标移动键*/
#define KEYINVALID 3/*无效键*/
/*定义符号常量: 真, 假 --- 真为1, 假为0 */
#define TRUE 1
#define FALSE 0
/**********************************************************/
/* 定义数据结构 */
/*棋盘交叉点坐标的数据结构*/
struct point
{
int x,y;
};
/**********************************************************/
/*自定义函数原型说明 */
void Init(void);
int GetKey(void);
int CheckKey(int press);
int ChangeOrder(void);
int ChessGo(int Order,struct point Cursor);
void DoError(void);
void DoOK(void);
void DoWin(int Order);
void MoveCursor(int Order,int press);
void DrawCross(int x,int y);
void DrawMap(void);
int JudgeWin(int Order,struct point Cursor);
int JudgeWinLine(int Order,struct point Cursor,int direction);
void ShowOrderMsg(int Order);
void EndGame(void);
/**********************************************************/
/**********************************************************/
/* 定义全局变量 */
int gPlayOrder; /*指示当前行棋方 */
struct point gCursor; /*光标在棋盘上的位置 */
char gChessBoard[19][19];/*用于记录棋盘上各点的状态*/
/**********************************************************/
/**********************************************************/
/*主函数*/
void main()
{
int press;
int bOutWhile=FALSE;/*退出循环标志*/
printf("Welcomewww.schoolhacker.com");
Init();/*初始化图象，数据*/
while(1)
{
press=GetKey();/*获取用户的按键值*/
switch(CheckKey(press))/*判断按键类别*/
{
/*是退出键*/
case KEYEXIT:
clrscr();/*清屏*/
bOutWhile = TRUE;
break;
/*是落子键*/
case KEYFALLCHESS:
if(ChessGo(gPlayOrder,gCursor)==FALSE)/*走棋*/
DoError();/*落子错误*/
else
{
DoOK();/*落子正确*/
/*如果当前行棋方赢棋*/
if(JudgeWin(gPlayOrder,gCursor)==TRUE)
{
DoWin(gPlayOrder);
bOutWhile = TRUE;/*退出循环标志置为真*/
}
/*否则*/
else
/*交换行棋方*/
ChangeOrder();
ShowOrderMsg(gPlayOrder);
}
break;
/*是光标移动键*/
case KEYMOVECURSOR:
MoveCursor(gPlayOrder,press);
break;
/*是无效键*/
case KEYINVALID:
break;
}
if(bOutWhile==TRUE)
break;
}
/*游戏结束*/
EndGame();
}
/**********************************************************/
/*界面初始化，数据初始化*/
void Init(void)
{
int i,j;
char *Msg[]=
{
"Player1 key:",
" UP----w",
" DOWN--s",
" LEFT--a",
" RIGHT-d",
" DO----space",
"",
"Player2 key:",
" UP----up",
" DOWN--down",
" LEFT--left",
" RIGHT-right",
" DO----ENTER",
"",
"exit game:",
" ESC",
NULL,
};
/* 先手方为1号玩家 */
gPlayOrder = CHESS1;
/* 棋盘数据清零, 即棋盘上各点开始的时候都没有棋子 */
for(i=0;i<19;i++)
for(j=0;j<19;j++)
gChessBoard[i][j]=CHESSNULL;
/*光标初始位置*/
gCursor.x=gCursor.y=0;
/*画棋盘*/
textmode(C40);
DrawMap();
/*显示操作键说明*/
i=0;
textcolor(BROWN);
while(Msg[i]!=NULL)
{
gotoxy(25,3+i);
cputs(Msg[i]);
i++;
}
/*显示当前行棋方*/
ShowOrderMsg(gPlayOrder);
/*光标移至棋盘的左上角点处*/
gotoxy(gCursor.x+MAPXOFT,gCursor.y+MAPYOFT);
}
/*画棋盘*/
void DrawMap(void)
{
int i,j;
clrscr();
for(i=0;i<19;i++)
for(j=0;j<19;j++)
DrawCross(i,j);
}
/*画棋盘上的交叉点*/
扩展：c语言五子棋游戏 / 五子棋游戏设计与实现 / 五子棋c语言代码
扩展：c语言五子棋游戏 / 五子棋游戏设计与实现 / 五子棋c语言代码
扩展：c语言五子棋游戏 / 五子棋游戏设计与实现 / 五子棋c语言代码
三 : 一步一步实现扫雷游戏（C语言实现）(一)
此项目相关博文链接
一步一步实现扫雷游戏（C语言实现）(一）
一步一步实现扫雷游戏（C语言实现）(二)
一步一步实现扫雷游戏（C语言实现）(三)
一步一步实现扫雷游戏（C语言实现）(四)
预定义：
#define MAX_X 100 //行坐标最大值
#define MAX_Y 100 //纵坐标最大值
全局数组：
char map[MAX_X][MAX_Y];
//为坐标数组，存储着地雷的分布
int m,n;
//为坐标的大小（选择等级时用的上）
//注意：MAX_X,MAX_Y与m,n的不同之处
算法函数接口：
1.返回周围地雷个数的函数
/****************************************************************************
返回周围地雷个数的函数
函数原型： int round_num_mines(int i,int j);
参 数： int i, int j为当前的坐标
返回值类型： int 返回该坐标处周围的地雷数
返回值情况：（1）返回1-8代表周围有1-8个地雷；
（2）返回0代表周围没有地雷；
（3）返回*代表此坐标时地雷；
******************************************************************************/
char round_num_mines(int i,int j)
{
int k =0;//记录周围地雷个数
if (map[i][j] =='*')
{
return'*';
}
else
{
if (i ==0) //第0行
{
if (j ==0) //第0行第0列
{
if (map[i][j+1] =='*') k++;
if (map[i+1][j] =='*') k++;
if (map[i+1][j+1] =='*') k++;
}
elseif (j == n-1) //第0行第n-1列
{
if (map[i+1][j] =='*') k++;
if (map[i][j-1] =='*') k++;
if (map[i+1][j-1] =='*') k++;
}
else//第0行非第0列非第n-1列
{
if (map[i][j-1] =='*') k++;
if (map[i][j+1] =='*') k++;
if (map[i+1][j-1] =='*') k++;
if (map[i+1][j] =='*') k++;
if (map[i+1][j+1] =='*') k++;
}
}
elseif (i == m-1) //第m-1行
{
if (j ==1) //第m-1行第0列
{
if (map[i][j+1] =='*') k++;
if (map[i-1][j] =='*') k++;
if (map[i-1][j+1] =='*') k++;
}
elseif (j == n-1) //第m-1行第n-1列
{
if (map[i-1][j] =='*') k++;
if (map[i][j-1] =='*') k++;
if (map[i-1][j-1] =='*') k++;
}
else//第m-1行非第0列非第n-1列
{
if (map[i][j+1] =='*') k++;
if (map[i-1][j] =='*') k++;
if (map[i-1][j+1] =='*') k++;
if (map[i][j-1] =='*') k++;
if (map[i-1][j-1] =='*') k++;
}
}
else//非第0行也非第m-1行
{
if (j ==1) //非第0行第0列
{
if (map[i+1][j] =='*') k++;
if (map[i+1][j+1] =='*') k++;
if (map[i][j+1] =='*') k++;
if (map[i-1][j] =='*') k++;
if (map[i-1][j+1] =='*') k++;
}
elseif (j == n-1) //非第0行第n-1列
{
if (map[i+1][j] =='*') k++;
if (map[i+1][j-1] =='*') k++;
if (map[i-1][j] =='*') k++;
if (map[i][j-1] =='*') k++;
if (map[i-1][j-1] =='*') k++;
}
else//非第0行非第0列非第m-1列
{
if (map[i+1][j] =='*') k++;
if (map[i+1][j-1] =='*') k++;
if (map[i+1][j+1] =='*') k++;
if (map[i][j+1] =='*') k++;
if (map[i-1][j] =='*') k++;
if (map[i-1][j+1] =='*') k++;
if (map[i][j-1] =='*') k++;
if (map[i-1][j-1] =='*') k++;
}
}
}
return k;
}
2.鼠标左键（扫雷）的函数
函数原型：void left_mouse(int i,int j);
参数：
int i, int j为当前的坐标
返回值类型：void
函数实现情况：（1）判断i，j；
（2）调用函数num_mines（）；
（3）判断函数num_mines（）的返回值：
1）返回1-8则在坐标点上画出1-8，此函数的功能完毕，return；
2）返回0则继续调用函数num_mines（），再递归调用函数left_mouse（）；
3）返回‘*’说明踩到地雷，return, game over!
3.右键（画出旗帜）的函数
此函数的主要功能是限制此位置，规定该位置不会被显示出数字或‘*’
4.初始化地雷分布位置和个数
/*******************************************************************
函数功能：根据设置的地雷个数和分布地图（map，数组）给出分布好了地雷的数组
函数原型：void set_mines(int num_mines)
参数：（in）—— int num_mines
*********************************************************************/
void set_mines(int num_mines)
{
int num =0;
while (num <= num_mines)
{
rand_mines(m, n);
//如果出现相同的情况呢？，没事，再循环几次，直到有了足够的地雷为止
num = fun_num_mines(m, n);//判断地雷个数
}
}
//设置随机选取(i,j),设置a[i][j] = '*'
void rand_mines(int m, int n)
{
int i,j;
srand(time(0));
//rand()%n 取(0，n-1)的随机数
i = rand() % m;
j = rand() % n;
map[i][j] ='*';
}
//判断地雷个数
int fun_num_mines(int m, int n)
{
int i,j, k =0;
for (i =0; i < m; i++)
{
for (j =0; j < n; j++)
{
if (map[i][j] =='*')
{
k++;
}
61阅读| 精彩专题| 最新文章| 热门文章| 苏ICP备13036349号-1