用游戏串起程序员的基本功之二

核心提示：第一篇我们用数组实现了洗牌的步骤，当然还有其他的方法，用游戏串起程序员的基本功之二，这也就是编程的带给我们的乐趣——灵活，自由，但交换次数仍没减少，下面是其代码：void paixu（）//用折半排序法 {for (int i = 1; i < =13; i++){int temp = apai[i]; //取得

　　第一篇我们用数组实现了洗牌的步骤。当然还有其他的方法。这也就是编程的带给我们的乐趣——灵活，自由。只要你想不得到，没有你做不到的。

　　今天我们就来实现第二步。掷色子，发牌。

　　掷色子的问题，其实很简单，但涉及到动画制作的原理。所以我们先来补充些这方面的知识。

　　我们知道，人的视觉都有一种现象，比如当你在黑暗中看灯泡时，忽然灯泡熄灭了，但灯泡发光的影像还会在我们眼前停几秒钟，这就是我们熟知的“视觉暂留效果”。我们所看到的电视、电影，包括我们说熟知的Flash，Director等动画制作软件，都是依靠这个效果才实现的。当我们在高速状态下（一般是每秒24帧），按一定的顺序切换内容相近和连贯的一组图片时，我们看到的不是一张张单独的图片影像，而是一段连贯的动画。

　　根据这个原理。我们掷色子的动画也就很轻易实现了。只要我们快速的变换不同点数的色子6个面，就会让人觉得好象是真实的转动着的色子了。你不用担心，运行速度的问题，只要你的机子能看vcd，一般都没问题。先看看下面的代码框架：

void zhisaizi（）
{
　int i；
　i= （int）5*rand（）+1；
　switch（i）
　　case 1：
　　　//载入第一张图片
　　case 2：
　　　//载入第二张图片
　　case 3：
　　。。。。。。//省略中间过程
　　case 6：
　　　//载入第六张图片
}
　　至于怎样载入和现实图像不是我们本篇的主要内容，大家可以学习《windows程序设计》这本书。

　　对于发牌的问题，我想大家应该不会在有问题了。这里我只给出代码，其中有具体的注释，就不解释了。下面是代码：

int apai[13]，bpai[13]；
//apai，bpai分别代表两玩家手中的牌，假如你做的是四个人
//的麻将，可你在自由扩展

void fapai（）
{
　int a，b；
　int i；//i代表发牌的起始位置
　if（（i/2）= =0）//是否为偶数
　　apai[a++]=pai[i++]； //双数牌发给a玩家
　else
　　bpai[b++]=pai[i++]；//单数牌发给b玩家
}
　　下面是我们本篇要讲的重点：就是在玩家都拿到牌之后，我们需要按顺序摆放好牌。这里我们会更加深入的谈到数据结构方面的一些知识，希望大家专心。

　　对于这个问题实质上也就是排序的问题。我们前面用136个整型数来代表136张牌，可以用1~136分别表示1~9万，1~9条，1~9饼，以及东南西北红中发财，也可以用1~39中的个位数分别对应着和他相等的1~9万，如3、13、23、33分别代表四张3万。其他以此类推。剩余的数字来表示东南西北红中发财。这个就可以由自己决定了。在此我们选择第一种方法来描述问题。

　　那么就请怎样排序呢?最轻易想到的方法是：取得一个数，和他前面的所有数比较，直到找到一个前面的数比它小，后面的数比他大的位置，并将其放入其中。再取得下一个数，继续上面的步骤。

　　示例如下：

8 7 4 3 6 1 //是要排序的数值
7 8 4 3 6 1 //第一次，取得7，小于前面的8，交换位置
7 4 8 3 6 1 //第二次，取得4，小于前面的8，交换位置
4 7 8 3 6 1 //第三次，小于再前面的7，交换位置
4 7 3 8 6 1 //第四次，取得3，小于前面的8，交换位置
4 3 7 8 6 1 //第五次，小于再前面的7，交换位置
3 4 7 8 6 1 //第六次，小于再前面的4，交换位置
3 4 7 6 8 1 //第七次，取得6，小于前面的8，交换位置
3 4 6 7 8 1 //第八次，小于再前面的7，交换位置
3 4 6 7 1 8 //第九次，取得1，小于前面的8，交换位置
3 4 6 1 7 8 //第十次，小于再前面的7，交换位置
3 4 1 6 7 8 //第十一次，小于再前面的6，交换位置
3 1 4 6 7 8 //第十二次，小于在前面的4，交换位置
1 3 4 6 7 8 //第十三次，小于再前面的3，交换位置

　　我们把这种方法叫做“插入排序法”。下面是源代码。

void paixu （）// 用插入排序法
{
　for (int i = 1; i <=13; i++)
　{
　　int temp = apai[i];//取得一个数
　　int j；
　　for ( j = i; j > 0 && temp < apai[j - 1]; j--) //和他前面的每一个数进行比较，
　　　apai[j] = apai[j - 1]; //假如这个数小于她前面的数就交换
　　　apai[j] = temp;//插入到正确位置
　}//end for
}//end
　　我们先来分析一下这种算法。可以看到，为了找到合适的插入位置，我们要用取得的数值与他前面的所有数值进行比较，并将进行多次的交换位置。尤其是当较小的数值放得越靠后时，交换到合适的位置所需的时间越长，如示例中的6和1，位置都靠后且相邻，但6放置到合适的位置只用了两步，而1放置到合适的位置却用了五步。

　　有没有其他的方法呢？针对比较次数和交换次数较多，我们可以用另一种“折半插入排序法”。基本思路是：为了减少比较的次数，我们不用每个数都比较，而是先找到所取得的数值在数组中的位置，并找到它前面已排好顺序的数组的中间的一个数值，比较两数，假如取得的数值大，就与後面的数值的中间数值比较，一直下去，直到找到合适的位置；同理假如所取得的数值小，就与前面的数值的中间数值比较，一直下去，直到找到合适的位置。

　　下面是示例：


8 7 4 3 6 1 //是要排序的数值
7 8 4 3 6 1 //第一次，取得7，小于前面的8，交换位置
7 4 8 3 6 1 //第二次，取得4，小于前面的8，交换位置
4 7 8 3 6 1 //第三次，小于再前面的7，交换位置
3 4 7 8 6 1 //第四次，取得3，小于前面的数组（4 7 8）中的中间数值7比较，小于7，所以比较数组（4 7）中间数值4，大于4，并交换到合适位置
3 4 6 7 8 1 //第五次，取得6，小于前面的数组（3 4 7 8）中的7，再与再靠前的数组（3 4 7）中间值4比较，大于4，交换位置
1 3 4 7 8 6 //第六次，取得1，小于再前面的数组（3 4 6 7 8）中间值6，再与数组
（3 4 6）中间值4比较，小于4，最后与数组（3 4）中间值3 比较，
小于3，交换位置

　　很明显这种方法的减少了比较的次数，但交换次数仍没减少。下面是其代码：

void paixu（）//用折半排序法
{
　for (int i = 1; i < =13; i++)
　{
　　int temp = apai[i]; //取得数值
　　int low = 0, high = i - 1;//low，high，分别表示比较范围的上下限
　　 while (low <= high)//折半查找
　　{
　　　int mid = (low + high) / 2; //取得中间位置
　　　if ( temp < apai[mid]) //假如小于中间位置的值
　　　　high = mid - 1; //从新确定下限
　　　else //假如大于中间位置的值
　　　　low = mid + 1; //从新确定上限
　　}//end while
　　for (int j = i - 1; j >= low; j--)
　　　apai[j + 1] = apai[j]; //记录后移
　　　apai[low] = temp; //插入到合适位置
　}//end for
}//end