logo资料库

游戏开发常用算法.doc

发布时间：2022-06-14 发布人：admin 分类：说明书 资料大小：0.12M 资料格式：doc 举报 版权申诉
第1页 / 共83页
第2页 / 共83页
第3页 / 共83页
第4页 / 共83页
第5页 / 共83页
第6页 / 共83页
第7页 / 共83页
第8页 / 共83页
资料共83页，剩余部分请下载后查看
    要使计算机能完成人们预定的工作，首先必须为如何完成预定的 工作设计一个算法，然后再根据算法编写程序。计算机程序要对 问题的每个对象和处理规则给出正确详尽的描述，其中程序的数 据结构和变量用来描述问题的对象，程序结构、函数和语句用来 描述问题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械 地执行的、有确定结果的指令组成。指令正确地描述了要完成的 任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行 算法的指令能在有限的步骤内终止，或终止于给出问题的解，或 终止于指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法可供选择，选择的主要标准 是算法的正确性和可靠性，简单性和易理解性。其次是算法所需 要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要 有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动 态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算 法设计时又常常采用递归技术，用递归描述算法。 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方 法。设方程为 f(x)=0，用某种数学方法导出等价的形式 x=g(x)，
    然后按以下步骤执行： （1） 选一个方程的近似根，赋给变量 x0； （2） 将 x0 的值保存于变量 x1，然后计算 g(x1)，并将结果存 于变量 x0； （3） 当 x0 与 x1 的差的绝对值还小于指定的精度要求时，重复 步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按 上述方法求得的 x0 就认为是方程的根。上述算法用 C 程序的形 式表示为： 【算法】迭代法求方程的根 { x0=初始近似根； do { x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon)； printf(“方程的近似根是%f\n”，x0)； } 迭代算法也常用于求方程组的根，令 X=（x0，x1，…，xn-1） 设方程组为： xi=gi(X) (I=0，1，…，n-1) 则求方程组根的迭代算法可描述如下：
    【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x)； } while (delta>Epsilon)； for (i=0;i printf(“变量 x[%d]的近似根是 %f”，I，x)； printf(“\n”)； } 具体使用迭代法求根时应注意以下两种可能发生的情况： （1） 如果方程无解，算法求出的近似根序列就不会收敛，迭代 过程会变成死循环，因此在使用迭代算法前应先考察方程是否有 解，并在程序中对迭代的次数给予限制； （2） 方程虽然有解，但迭代公式选择不当，或迭代的初始近似 根选择不合理，也会导致迭代失败。 二、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚 举和检验，并从众找出那些符合要求的候选解作为问题的解。 【问题】 将 A、B、C、D、E、F 这六个变量排成如图所示的
    三角形，这六个变量分别取[1，6]上的整数，且均不相同。求使 三角形三条边上的变量之和相等的全部解。如图就是一个解。 程序引入变量 a、b、c、d、e、f，并让它们分别顺序取 1 至 6 的证书，在它们互不相同的条件下，测试由它们排成的如图所示 的三角形三条边上的变量之和是否相等，如相等即为一种满足要 求的排列，把它们输出。当这些变量取尽所有的组合后，程序就 可得到全部可能的解。细节见下面的程序。 【程序 1】 # include void main() { int a,b,c,d,e,f; for (a=1;a<=6;a++) for (b=1;b<=6;b++) { if (b==a) continue; for (c=1;c<=6;c++) { if (c==a)||(c==b) continue; for (d=1;d<=6;d++) { if (d==a)||(d==b)||(d==c) continue; for (e=1;e<=6;e++) { if (e==a)||(e==b)||(e==c)||(e==d) continue; f=21-(a+b+c+d+e); if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {
    printf(“%6d,a); printf(“%4d%4d”,b,f); printf(“%2d%4d%4d”,c,d,e); scanf(“%*c”); } } } } } } 按穷举法编写的程序通常不能适应变化的情况。如问题改成有 9 个变量排成三角形，每条边有 4 个变量的情况，程序的循环重数 就要相应改变。 对一组数穷尽所有排列，还有更直接的方法。将一个排列看作一 个长整数，则所有排列对应着一组整数。将这组整数按从小到大 的顺序排列排成一个整数，从对应最小的整数开始。按数列的递 增顺序逐一列举每个排列对应的每个整数，这能更有效地完成排 列的穷举。从一个排列找出对应数列的下一个排列可在当前排列 的基础上作部分调整来实现。倘若当前排列为 1，2，4，6，5， 3，并令其对应的长整数为 124653。要寻找比长整数 124653 更 大的排列，可从该排列的最后一个数字顺序向前逐位考察，当发 现排列中的某个数字比它前一个数字大时，如本例中的 6 比它的
    前一位数字 4 大，这说明还有对应更大整数的排列。但为了顺序 从小到大列举出所有的排列，不能立即调整得太大，如本例中将 数字 6 与数字 4 交换得到的排列 126453 就不是排列 124653 的下 一个排列。为了得到排列 124653 的下一个排列，应从已经考察 过的那部分数字中选出比数字大，但又是它们中最小的那一个数 字，比如数字 5，与数字 4 交换。该数字也是从后向前考察过程 中第一个比 4 大的数字。5 与 4 交换后，得到排列 125643。在前 面数字 1，2，5 固定的情况下，还应选择对应最小整数的那个排 列，为此还需将后面那部分数字的排列顺序颠倒，如将数字 6， 4，3 的排列顺序颠倒，得到排列 1，2，5，3，4，6，这才是排 列 1，2，4，6，5，3 的下一个排列。按以上想法编写的程序如 下。 【程序 2】 # include # define SIDE_N 3 # define LENGTH 3 # define VARIABLES 6 int A,B,C,D,E,F; int *pt[]={&A,&B,&C,&D,&E,&F}; int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,& A};
    int side_total[SIDE_N]; main{} { int i,j,t,equal; for (j=0;j while(1) *pt[j]=j+1; { for (i=0;i { for (t=j=0;j t+=*side[i][j]; side_total[i]=t; } for (equal=1,i=0;equal&&i if (side_total[i]!=side_total[i+1] equal=0; if (equal) { for (i=1;i printf(“%4d”,*pt[i]); printf(“\n”); scanf(“%*c”); } for (j=VARIABLES-1;j>0;j--) if (*pt[j]>*pt[j-1]) break; if (j==0) break; for (i=VARIABLES-1;i>=j;i--) if (*pt[i]>*pt[i-1]) break; t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t; for (i=VARIABLES-1;i>j;i--,j++)
    { t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; } } } 从上述问题解决的方法中，最重要的因素就是确定某种方法来确 定所有的候选解。下面再用一个示例来加以说明。 【问题】 背包问题 问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物 品中选取一部分物品的选择方案，使选中物品的总重量不超过指 定的限制重量，但选中物品的价值之和最大。 设 n 个物品的重量和价值分别存储于数组 w[ ]和 v[ ]中，限制重 量为 tw。考虑一个 n 元组（x0，x1，…，xn-1），其中 xi=0 表 示第 i 个物品没有选取，而 xi=1 则表示第 i 个物品被选取。显然 这个 n 元组等价于一个选择方案。用枚举法解决背包问题，需要 枚举所有的选取方案，而根据上述方法，我们只要枚举所有的 n 元组，就可以得到问题的解。 显然，每个分量取值为 0 或 1 的 n 元组的个数共为 2n 个。而每 个 n 元组其实对应了一个长度为 n 的二进制数，且这些二进制 数的取值范围为 0～2n-1。因此，如果把 0～2n-1 分别转化为相 应的二进制数，则可以得到我们所需要的 2n 个 n 元组。 【算法】 maxv=0; for (i=0;i<2n;i++)
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料