八皇后问题的一维数组解法
#include
#include
#include
void calc();
int main (void)
{
calc();
system("PAUSE");
return 0;
}
void calc()
{ long int i,j,k,range,number=0;
short int judge;
printf("Please enter the lenth of each line;");
scanf("%ld",&range); /*range用于存储棋盘的边的长度*/
time_t timep;
time (&timep);
printf("%s",ctime(&timep)); /*打出开始运行的时间*/
long int record[range];
for (k=0;k {record[k]=k;} for(;1;) /*创建无限循环以保证能取到所有情况*/ { judge=1; for(i=0;i { for(j=0;j /*终止循环，将不合题意的皇后后移一位，重新判断*/ { if (record[i]==record[j] || record[i]-record[j]==i-j || record[j]-record[i]==i-j) { judge=0; if(record[i] { record[i]++; for(k=i+1;k {record[k]=k-i-1;} } else if (record[i-1] { record[i-1]++; for(k=i;k {record[k]=k-i;} } else if(i<2) { time_t timep; /*循环到第一列的皇后在该列最后一格时停止循环*/ time (&timep); printf("%s",ctime(&timep)); printf("In that case,there are %ld solutions.",number); return; } else { record[i-2]++; for(k=i-1;k {record[k]=k-i+1;} } break; } else continue; } if (judge==0) break; } if (judge==1) { number++; } else continue; j=range-1; for(;j>=0;j--) /*如果当前布局满足条件，就正常进行下一次穷举*/ { if(record[j] { record[j]++; for(k=j+1;k {record[k]=k-j-1;} break; } else { if(j>0) continue; else { time_t timep; time (&timep); printf("%s",ctime(&timep)); printf("In that case,there are %ld solutions.",number); return ; } } } } } 要用指针处理二维数组，首先要解决从存储的角度对二维数组的认识问题。我们知道，一个二维数组在计算机中存储时，是按照先行后列的顺序依次存储的，当把每一行看作一个整体，即视为一个大的数组元素时，这个存储的二维数组也就变成了一个一维数组了。而每个大数组元素对应二维数组的一行，我们就称之为行数组元素，显然每个行数组元素都是一个一维数组 下面我们讨论指针和二维数组元素的对应关系，清楚了二者之间的关系，就能用指针处理二维数组了。 设p是指向数组a的指针变量，若有： p=a[0]; 则p+j将指向a[0]数组中的元素a[0][j]。 由于a[0]、a[1]┅a[M-1]等各个行数组依次连续存储，则对于a数组中的任一元素a[i][j]，指针的一般形式如下： p+i*N+j 元素a[i][j]相应的指针表示为： *( p+i*N+j) 同样，a[i][j]也可使用指针下标法表示，如下： p[i*N+j] 例如，有如下定义： int a[3][4]={{10,20,30,40,},{50,60,70,80},{90,91,92,93}}; 则数组a有3个元素，分别为a[0]、a[1]、a[2]。而每个元素都是一个一维数组，各包含4个元素，如a[1]的4个元素是a[1][0]、a[1][1]、a[1]2]、a[1][3]。 若有： int *p=a[0]; 则数组a的元素a[1][2]对应的指针为：p+1*4+2 元素a[1][2]也就可以表示为：*( p+1*4+2) 用下标表示法，a[1][2]表示为：p[1*4+2] 特别说明： 对上述二维数组a，虽然a[0]、a都是数组首地址，但二者指向的对象不同，a[0]是一维数组的名字，它指向的是a[0]数组的首元素，对其进行“*”运算，得到的是一个数组元素值，即a[0]数组首元素值，*a等价于a[0] a[0]等价于&a[0][0],因此，*a[0]与a[0][0]是同一个值； 实验六一维数组程序设计 一、实验学时 2学时 二、实验目的 （一）掌握一维数组的定义、初始化方法； （二）掌握一维数组中数据的输入和输出方法； （三）掌握与一维数组有关的程序和算法； （四）了解用数组处理大量数据时的优越性。 三、预习要求 （一）理解数组的概念、利用数组存放数据有何特点； （二）一维数组的定义、初始化方法； （三）一维数组中数据的输入和输出方法。 四、实验内容 （一）下面的几个程序都能为数组元素赋值，请输入程序并运行。比较一下这些赋值方法的异同。 １．在定义数组的同时对数组初始化。 /* c6-1.c */ /*在定义数组的同时对数组初始化*/ #include "stdio.h" void main( ) { int a[4]={0,1,2,3}; printf("\n%d %d %d %d\n",a[0],a[1],a[2],a[3]); } 2．不使用循环对单个数组元素赋值。 /* c6-2.c */ /*不使用循环对单个数组元素赋值*/ #include "stdio.h" void main( ) { int a[4]; a[0]=2;a[1]=4;a[2]=6;a[3]=8; printf("\n%d %d %d %d\n",a[0],a[1],a[2],a[3]); } 3．用循环结构，从键盘输入为每个数组元素赋值，输出各数组元素。 /* c6-3.c */ /*利用循环通过键盘对数组元素赋值*/ #include "stdio.h" void main( ) { int i,a[4]; for(i=0; i<4; i++) scanf("%d",&a[i]); printf("\n"); for(i=0; i<4; i++) printf("%d ",a[i]); 题目：定义一个一维数组存储10个学生名字；定义一个二维数组存储这10个学生的6门课（C程序设计、物理、英语、高数、体育、政治）的成绩； 程序应具有下列功能： （1）按名字查询某位同学成绩 （2）查询某个科目不及格的人数，及学生名单 代码如下： import java.util.*; public class Test{ public static void main(String[]args){ Scanner input=new Scanner(System.in); String[]name={"a","b","c","d","e","f","g","h","i","l"};//存储学生的名字 int[][] grade={{50,60,70,80,90,10},{40,90,80,60,40,70},{60,80,70,60,40,90},{50,60,70,80,90,10}, {60,80,70,60,40,90},{60,70,80,90,70,70},{60,80,70,60,40,90},{60,80,70,60,40,90},{70, 80,90,70,70,70},{60,80,70,60,40,90}};//存储学生各科成绩 System.out.println("输入要查询成绩的学生名字："); String chioce=input.nextLine(); for(int i=0;i<10;i++) { if(name[i].equals(chioce)) {System.out.println("学生："+name[i]+"的成绩如下："); System.out.println("C程序设计："+grade[i][0]+"物理："+grade[i][1]+"英 语:"+grade[i][2]+"高数:"+grade[i][3]+"体育:"+grade[i][4]+"政治:"+grade[i][5]+"\n"); break;} } System.out.println("******************************************************"); 数组的元素也可以是数组，每个数组的一个元素都是由一个一维数组构成，被称为二维数组。同样，多维数组可以看作是数组的数组，即N维数组的每一个元素就是一个N-1维数组。如：三维数组中的每一个元素都是一个二维数组。多维数组的定义即初始化与二维数组的基本类似，因此本节主要讲述二维数组。 1 、二维数组的声明 二维数组声明的一般格式如下： 数据类型数组名[][]; 或者格式如下： 数据类型[][] 数组名; 其中数据类型与一维数组的相同，它既可以是基本数据类型，也可以是复合数据类型，数组名可以是任意合法的变量名。下面是数组声明举例。 char ch[][]; double[][] d; String[][] str; 与一维数组的声明相同，二维数组也不需要规定其中任意一维的长度，下面的声明都是不合法的。 char ch[4][]; double[][5] d; String[6][7] str; 2、二维数组的初始化 二维数组的初始化也分为直接初始化和动态初始化两种方式。直接初始化必须在声明时开始，如下 ··124面的例子所示。 int array[][] = {{1,2},{2,4},{4,8}}; 二维数组的动态初始化又可分为两种方式：一种是直接规定每一维的长度，并分配所需的内存空间，另一种是从高维开始，分别为每一维规定长度并分配内存空间。 直接为每一维分配内存的格式如下： 变量名= new 数据类型[二维长度][一维长度]; 其中二维长度和一维长度都是大于0的整数，如下所示。 int array[][]; array = new int[3][5]; array是一个二维数组，二维长度为3，array[0]、array[1]、array[2]都是一维数组，长度都是5。分别分配内存格式如下： 变量名= new 数据类型[二维长度][]; 变量名[0] = new 数据类型[一维长度0]; 变量名[1] = new 数据类型[一维长度1]; 变量名[2] = new 数据类型[一维长度2]; ... 变量名[二维长度-1] = new 数据类型[一维长度n]; 下面是一个二维数组初始化的实例。 Int array[][]; //声明int类型二维数组array A = new int[3][]; //为二维分配内存空间 A[0] = new int[5]; //为A[0]的一维分配内存空间 A[1] = new int[5]; //为A[1]的一维分配内存空间 A[2] = new int[5]; //为A[2]的一维分配内存空间 3、二维数组的空间模型 1.引子 中国有一句古话，叫做“不撞南墙不回头"，生动的说明了一个人的固执，有点贬义，但是在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法，最终达到目的地。当然整个过程需要很多往返，这样的前进方式，效率比较低下。 2.适用范围 适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。 3.应用场景 在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。国际象棋的棋盘如下图所示： 4.分析 基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后 q(row,col)吃掉 1）x=row(在纵向不能有两个皇后) 2) y=col（横向） 3）col + row = y+x;（斜向正方向） 4) col - row = y-x;（斜向反方向） 遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。 我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,80) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置，而第五列，我们会发现找不到皇后的安全位置了，前面四列的摆放如下: 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制 一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i 工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11) 参考文献 (12) . 1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析 thinkphp将二维数组变为标签适用的一维数组 2012-01-10 11:23:31| 分类：默认分类|字号订阅 方法一： $projectList=arr1tag($projectList,array('','请选择'),'project_name'); //其中$list为传值过来的二维数组，$default为默认值，$k为指定的表字段function arr1tag($list,$default='',$k=''){ $tmp=''; if(array($list)){ if(array($default)){ $tmp[$default[0]]=$default[1]; } foreach ($list as $k1=>$v1){ $tmp[$k1+1]=$v1[$k]; } } return $tmp; } 方法二： $projectList=arr2tag($projectList,array('','请选择'),''); //根据数组下标获取对应值 function array_index2val($array,$index=0){ $value=''; if(is_array($array)){ $i=0; foreach($array as $val){ if($i===$index){ $value=$val; break; } $i++; } } return $value; } //把数据库中调出的数组转换成可以使用模版标签的数组，其中$default为默认值，$k为指定的表字段 function arr2tag($arr,$default=NULL,$K=NULL){ $tmp=''; if(is_array($arr)){ if(is_array($default)){ $tmp[$default[0]]=$default[1]; if($type==1){ $tmp[$default[2]]=$default[3]; } } foreach ($arr as $key=>$val){ if(is_array($K)){ $tmp[$val[$K[0]]]=$val[$K[1]]; }else{ $tmp[array_index2val($val,0)]=array_index2val($val,1); } } } return $tmp; } 方法三： 将读取数据库的内容直接转换为一维数组,该方法大多用于select标签 $this->where($where)->getField('id,name'); 得出的内容为 array( 二维数组 我们以前学过的数组叫一维数组（只有一行） 二维数组，有行有列 0 1 2 3 0 1 2 3 4 1 5 6 7 8 2 9 10 11 12 如何来定义二维数组 格式：类型标识符数组名[行的长度][列的长度]； Int a[3][4] 讨论一下究竟有多少元素？元素个数=行的长度*列的长度意义：定义了一个二维数组名为A含有12个元素，每个元素都是一个整形变量，他们是： a[0][1],a[0][2]…对于第一行而言，行的下标都是零。 规律：对于每一行而言，行的下标不会改变，列的下标改变。 给二维数组赋初值（实际上是给二维数组中的每个元素付出只）1）int a[3][4]={1,2,3,4, 5,6,7,8, 9,10,11,12} ; 必须要会认，最基本的，比如a[2][0],分组后是9 2)int a[3][4]={1,2,3,4},{5,6,7,8}{9,10,11,12}; 3)可以省略行，但不能省略列 A：iint a[][4]= {1,2,3,4, 5,6,7,8, 9,10,11,12} ; B:int a[][4] ={1,2,3,4},{5,6,7,8}{9,10,11,12}; 4) int a[3][4]={1,2,3,4, 5,6,7,8, 9,10,11} ;可以少赋值，自动填0 a[2][3]=0 5) int a[][4] ={1,3,4},{5,6,7,8}{9,10,11,12}; a[0][3]=0 注意： 1)二维数组的复制原则，是要优先满足前面的行，然后再来满足后面的行 2)二维数组行的长度用来表明共有多少行，列的个数用来表明每行的元素个数 二维数组的输出 1）有数组就要循环 我们肯定要输出三行，每行要输出四个数据 第i行第j个元素：for(i=0;i<3(行的长度);i++) {for(j=0;j<4（列的长度）;j++) {printf(“%d”,a[i][j]);}//如果内循环做完了，表示第i行 就输出完了 printf(“/n”);} 淮阴工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 课题 名称 八皇后 设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程 序开发打下基础. 实验环境1）系统要求：win98以上操作系统；2）语言平台：tc++或vc++6.0；3）执行文件：八皇后.exe 任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 工作进度计划 序号起止日期工作内容 1 2008.6.23~2008.6.24查阅相关内容 2 2008.6.24~2008.6.25编写代码及实习报告 3 2008.6.25~2008.6.26完善课程设计报告 4 2008.6.26~2008.6.27答辩 指导教师（签章）： 2008 年 6 月30 日 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 八皇后问题 问题描述： 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突 （在每一横列，竖列，斜列只有一个皇后）。 求解： 标题: 八皇后问题的解（回溯法程序代码） 发信站: 网易虚拟社区(Fri Jul 14 10:06:52 2000),站内信件 以前上学的时候，写8皇后程序的时候偷懒用最笨的算法，在8086上计算十皇后的时候，我放了张纸条，说明计算机正在运行，然后去吃饭，吃完以后，才看到结果。前几天，刚好有空，所以重写了一次，以补当年的遗憾。 #include "stdio.h" int attacked(int *array,int position){ int flag=-1; float step; if(position==1) return flag; for(step= 1.00;step (array+(int)step)-*(array+position))/(step-position))==-1){ flag=1; break;}} return flag;}void main(void){ int countSum,queenSum,printCount,*queenArray,queenPosition=0; int tempArray[20]={66,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; countSum=1; queenArray=tempArray; printf("input you queenSum here: "); scanf("%d",&queenSum); fflush(stdin); if(queenSum<4){ printf("the %d queen's sum is 0\n",queenSum); return;}for(;;){ if(countSum 实验四二维数值数组 一、实验目的 (1)熟悉C语言关于“数组”的语法规则。 (2)掌握C语言程序中关于数值“数组”的应用技巧。 (3)掌握一维数组和二维数组的定义、赋值和输入输出的方法；数组元素的存储形式和引用方法； (4)掌握与数组有关的排序（选择法、冒泡法）、查找（顺序查找、折半查找）、有序数列的插入和删除操作等算法(特别是排序算法) 二、实验准备 1．C语言实现循环的方法 ①数组的定义： Int b[3][4]; \*二维数组b包含了3行4列个元素*\ ②数组的赋初值：定义数组的同时给元素赋值，可以整体赋值 Int b[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; \*按行进行赋值*\ Int b[][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}}; \*可以省略行下标，但不能省略列下标*\ Int b[3][4]={1,2,3,4,5,6,7,8,9,10,11,12}; \*也可以存储空间位序顺序赋值*\ ③数组元素的引用：数组元素只能单个应用如a[3][2]; ③数组元素的遍历： 二维数组用双重循环，外循环循环控制变量为行下标，内循环循环控制变量为列下标。 3．阅读以下程序，并分析其功能，调试运行程序后再分析其运行结果。 1 程序二，程序文件名为ex4-2.c。（掌握二维数组的输入输出，和转置） # include Dim int1 As Integer Private Sub cmd_click() List1.Clear int1 = 0 Dim i As Single, j As Single i = 1 j = 1 Dim p As Integer, b As Boolean Dim a(1 To 8, 1 To 8) As Boolean Dim ii(1 To 8) As Single Dim jj(1 To 8) As Single a(i, j) = True ii(1) = i jj(1) = j Do Do While i < 8 i = i + 1 If i = 0 Then Exit Sub j = 1 If b = True Then a(i, jj(i)) = False b = False j = jj(i) + 1 End If Do If j > 8 Then i = i - 2: b = True: Exit Do For p = 1 To i - 1 If j = jj(p) Or Abs(i - ii(p)) = Abs(j - jj(p)) Then Exit For Next If p = i Then Exit Do j = j + 1 Loop If b = False Then ii(i) = i: jj(i) = j a(i, j) = True End If Loop Dim p1 As Integer, p2 As Integer, str1 As String For p1 = 1 To 8 str1 = "" For p2 = 1 To 8 If a(p1, p2) = False Then str1 = str1 & "+ " Else: str1 = str1 & "@ " End If Next List1.AddItem str1 Next int1 = int1 + 1 Caption = int1 i = i - 1: b = True List1.AddItem " " & Str(int1) List1.AddItem vbCrLf Loop End Sub 窗体上一个list控件list1 一个按钮 cmd 回溯算法与八皇后问题(N皇后问题) 1 问题描述 八皇后问题是数据结构与算法这一门课中经典的一个问题。下面再来看一下这个问题的描述。八皇后问题说的是在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。更通用的描述就是有没有可能在一张N*N的棋盘上安全地放N个皇后？ 2 回溯算法 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。 下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘： 1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列 2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没 有两个皇后)，若不满足，跳到第4步 3) 在当前位置上满足条件的情形： 在当前位置放一个皇后，若当前行是最后一行，记录一个解； 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置； 若当前行是最后一行，当前列不是最后一列，当前列设为下一列； 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置； 以上返回到第2步 4) 在当前位置上不满足条件的情形： 若当前列不是最后一列，当前列设为下一列，返回到第2步; 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。 为了便于将上述算法编程实现，将它用另一种形式重写： Queen() Loop: if check_pos(curr_row, curr_col) == 1 then put_a_queen(curr_row, curr_col); if curr_row == N then record_a_solution(); end if; if curr_row != N then curr_row = curr_row + 1; curr_col = 1; else if curr_col != N then curr_col = curr_col + 1; else backtrack(); end if; end if; else if curr_col != N then 一维数组 排序 一、选择排序法： 数据已经放在一维数组中，要求从小到大排序。 数组 20 4 36 …… 45 109 3 下标 1 2 3 …… n-2 n-1 n 排序过程： 1、从第1项到第n项选择最小值，然后将第1项与最小项交换。 2、从第2项到第n项选择最小值，然后将第2项与最小项交换。 3、…… 4、从第n-1项到第n项选择最小值，然后将第n-1项与最小项交换。注意：最小值及下标由临时变量存储。 所以，需要两层循环：外层循环i执行n-1次，内层循环j执行n-i-1次For i=1 to n-1 最小值及下标由临时变量存储 tmpVal=第i项值 tmpId=第i项下标 For j=i+1 to n 若tmpVal >第j项值，则: tmpVal=第j项值 tmpId=第j项下标 next 将第i项与最小项交换 Next 从大到小呢？ 二、冒泡排序法： 数据已经放在一维数组中，要求从小到大排序。 数组 20 4 36 …… 45 109 3 下标 1 2 3 …… n-2 n-1 n 两种方法：小数上浮和大数下沉。 小数上浮排序过程：从第n项到第k项，依次相临两项比较，若第m项小于第m-1项，则两项交换。（k从2到n） 第1次执行：结果是第1项至第n项中的最小值放到第1项中 1、若第n项小于第n-1项，将第n项与第n-1项交换。 2、若第n-1项小于第n-2项，将第n-1项与第n-2项交换。 3、…… 4、若第2项小于第1项，将第2项与第1项交换。 第2次执行：结果是第2项至第n项中的最小值放到第2项中 1、若第n项小于第n-1项，将第n项与第n-1项交换。 2、若第n-1项小于第n-2项，将第n-1项与第n-2项交换。 3、…… 4、若第3项小于第2项，将第3项与第2项交换。 …… 第n-1次执行： 1、若第n项小于第n-1项，将第n项与第n-1项交换。 所以，需要两层循环：外层循环i执行n-1次，内层循环j执行n-i次 For i=1 to n-1 For j=n to i+1 step -1 若第j项值<第j-1项值，则: 指向二维数组的指针 一. 二维数组元素的地址 为了说明问题, 我们定义以下二维数组: int a[3][4]={{0,1,2,3}, {4,5,6,7}, {8,9,10,11}}; a为二维数组名, 此数组有3行4列, 共12个元素。但也可这样来理解, 数组a由三个元素组成: a[0], a[1], a[2]。而它中每个元素又是一个一维数组, 且都含有4个元素(相当于4列), 例如, a[0]所代表的一维数组所包含的4 个元素为a[0][0], a[0][1], a[0][2], a[0][3]。如图5.所示: ┏━━━━┓┏━┳━┳━┳━┓ a─→┃a[0] ┃─→┃0 ┃1 ┃2 ┃3 ┃ ┣━━━━┫┣━╋━╋━╋━┫ ┃a[1] ┃─→┃4 ┃5 ┃6 ┃7 ┃ ┣━━━━┫┣━╋━╋━╋━┫ ┃a[2] ┃─→┃8 ┃9 ┃10┃11┃ ┗━━━━┛┗━┻━┻━┻━┛ 图5. 但从二维数组的角度来看, a代表二维数组的首地址, 当然也可看成是二维数组第0行的首地址。a+1就代表第1行的首地址, a+2就代表第2行的首地址。如果此二维数组的首地址为1000, 由于第0行有4个整型元素, 所以a+1为1008, a+2 也就为1016。如图6.所示 a[3][4] a ┏━┳━┳━┳━┓ (1000)─→┃0 ┃1 ┃2 ┃3 ┃ a+1 ┣━╋━╋━╋━┫ (1008)─→┃4 ┃5 ┃6 ┃7 ┃ a+2 ┣━╋━╋━╋━┫ (1016)─→┃8 ┃9 ┃10┃11┃ ┗━┻━┻━┻━┛ 图6. 既然我们把a[0], a[1], a[2]看成是一维数组名, 可以认为它们分别代表它们所对应的数组的首地址, 也就是讲, a[0]代表第0 行中第0 列元素的地址, 即&a[0][0], a[1]是第1行中第0列元素的地址, 即&a[1][0], 根据地址运算规则, a[0]+1即代表第0行第1列元素的地址, 即&a[0][1], 一般而言, a[i]+j即代表第i行第j列元素的地址, 即&a[i][j]。 另外, 在二维数组中, 我们还可用指针的形式来表示各元素的地址。如前所述, a[0]与*(a+0)等价, a[1]与*(a+1)等价, 因此a[i]+j就与*(a+i)+j等价, 它表示数组元素a[i][j]的地址。 因此, 二维数组元素a[i][j]可表示成*(a[i]+j)或*(*(a+i)+j), 它们都与a[i][j]等价, 或者还可写成(*(a+i))[j]。 另外, 要补充说明一下, 如果你编写一个程序输出打印a和*a, 你可发现它们的值是相同的, 这是为什么呢? 我们可这样来理解: 首先, 为了说明问题, 我们把二维数组人为地看成由三个数组元素a[0], a[1], a[2]组成, 将a[0], a[1], a[2]看成是数组名它们又分别是由4个元素组成的一维数组。因此, a表示数组第0行的地址, 而*a即为a[0], 它是数组名, 当然还是地址, 它就是数组第0 行第0 列元素的地址。 C语言一维数组的定义和引用 在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在Ｃ语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。本章介绍数值数组和字符数组，其余的在以后各章陆续介绍。 7.1一维数组的定义和引用 7.1.1一维数组的定义方式 在Ｃ语言中使用数组必须先进行定义。一维数组的定义方式为：类型说明符数组名[常量表达式]； 其中：类型说明符是任一种基本数据类型或构造数据类型。数组名是用户定义的数组标识符。方括号中的常量表达式表示数据元素的个数，也称为数组的长度。 例如： int a[10]; 说明整型数组a，有10个元素。 float b[10],c[20]; 说明实型数组b，有10个元素，实型数组c，有20个元素。 char ch[20]; 说明字符数组ch，有20个元素。 对于数组类型说明应注意以下几点： 数组的类型实际上是指数组元素的取值类型。对于同一个数组，其所有元素的数据类型都是相同的。 数组名的书写规则应符合标识符的书写规定。 数组名不能与其它变量名相同。 例如： main() { int a; float a[10]; …… } 是错误的。 方括号中常量表达式表示数组元素的个数，如a[5]表示数组a有5个元素。但是其下标从0开始计算。因此5个元素分别为a[0],a[1],a[2],a[3],a[4]。 不能在方括号中用变量来表示元素的个数，但是可以是符号常数或常量表达式。 例如： #define FD 5 main() { int a[3+2],b[7+FD]; 回溯法解八皇后问题 在N * N 格的棋盘上放置彼此不受攻击的N 个皇后。N个皇后问题等价于在N * N 格的棋盘上放置N 个皇后，任何2个皇后不在同一行或同一列或同一斜线上。当N等于8，就是著名的八皇后问题。 此问题是通过C语言程序编写的，在Turboc环境下完成实现的。输出结果见（输出结果。TXT文件） 详细代码为： /*///////////////////////////////////////////////////////////////////// /// /////The programming is a complex problem about the ways of queens./////// /////Programmer: Luo Xiaochun /////// /////Completed date: 2007.12 //////// /////V ersion number: Turboc 2.0 //////// /////////////////////////////////////////////////////////////////////// /*/ #include Perl二维数组用法全程剖析 本文和大家重点讨论一下PerlPerl二维数组的概念，PerlPerl二维数组简单说就是数组的数组，创建一个数组的数组（有时也可以叫“列表的列表”，不过不太准确）真是再简单也不过了。请看下面详细介绍。 Perl二维数组 非常简短的一个Perl二维数组教程，由鄙人翻译完成。 最新版本可以从这里获取（POD格式）： https://www.doczj.com/doc/ea3840131.html,/trunk/POD2-CN/lib/POD2/CN/perllol.pod NAME perllol-操作数组的数组（Perl二维数组） 说明 Perl二维数组中声明和访问数组的数组 创建一个数组的数组（有时也可以叫“列表的列表”，不过不太准确）真是再简单也不过了。它相当容易理解，并且本文中出现的每个例子都有可能在实际应用中出现。 数组的数组就是一个普通的数组(@AoA)，不过可以接受两个下标("$AoA[3][2])。 下面先定义一个这样的数组： 1"#一个包含有“指向数组的引用”的数组 2@AoA=( 3["fred","barney"], 4["george","jane","elroy"], 5["homer","marge","bart"], 6); 7 8print$AoA[2][2]; 9bart 10 你可能已经注意到，外面的括号是圆括号，这是因为我们想要给数组赋值，所以需要圆括号。如果你*不*希望这里是@AoA，而是一个指向它的引用，那么就得这样：11#一个指向“包含有数组引用的数组”的引用 12$ref_to_AoA=[ 13["fred","barney","pebbles","bambam","dino",], 14["homer","bart","marge","maggie",], 15["george","jane","elroy","judy",], 16];二维数组和指针
实验六 一维数组程序设计
JAVA一维数组二维数组运用的例子
java数组之二维数组
八皇后解题思路
算法实验 递归回溯解八皇后问题
八皇后问题的解决完整文档
thinkphp将二维数组转换为一维数组
C语言笔记(二维数组-函数)
八皇后问题地解决完整文档
八皇后问题及解答
实验四 二维数值数组
八皇后问题vb解
回溯算法与八皇后问题N皇后问题Word版
vb中一维二维数组应用
指向二维数组的指针
C语言一维数组的定义和引用
回溯法解八皇后问题
二维数组
相关主题
文本预览