几种不同的算法实现小时候玩的扑克牌游戏

microjava

记得小时候看到别人玩的一个游戏，给他一定个数有大小次序的扑克牌，指定每次置底的个数，经过他调整次序后，可以先置底再出一张牌，依此类推，直到扑克牌全部出来，可以实现从大到小或者从小到大一个个出来，是怎么出来的呢？当时觉得很神奇，长大后经过思考和查阅知道了方法，并用几种算法实现了！
  
   以下是用java实现的程序：


/** * 功能说明：扑克牌游戏，先出一张牌后置一张牌到底部，依次类推 * 使其按1 2 3 4顺序出列 * 采用逆推法和改错法 */package com.mcfeng.base;/** * @author microjava *  * 2008-12-29上午12:46:15 *  */public class Pukepai {private final static int PAI_NUM = 13;/** * @param args */public static void main(String[] args) {// 测试// System.out.println(adNum(13));// 排序第一个参数为牌的个数，第二个参数为置底个数（目前只支持1）第三个参数0代表先出牌1代表先置底sort(13, 1, 0);//逆推法sortByNitui(13,3,true);//唐粒子的方法/*int num = 3;while(num++ < 1000) {sort(num, 1, 0);sortByTang(num);}*/}/** * 得出 n + n/2 + n/4 + ... + 1 的和 有小数的补整 */public static int adNum(int n) {int m = 0;for (int i = n; i > 0;) {// System.out.println(i);m += i;if (i == 1)break;if (i % 2 == 0)i = i / 2;elsei = (i / 2) + 1;}return m;}/** * 改错法 * 扑克牌排序，三个参数的意思分别为： paiNum牌个数 hNum每次置地步牌的个数 l出牌或置底顺序(0为先出牌，1为先置底) */public static int[] sort(int paiNum, int hNum, int l) {if(paiNum <= 1)  {int [] res = {1};return res;}int total = adNum(paiNum);int[] a = new int[total]; // 初始的加长数组 可以存放置底的牌 长度由 n + n/2 +// n/4 + ... + 1得出int[] b = new int[paiNum]; // 逆推序列数组int[] c = new int[paiNum]; // 正确顺序数组//初始化数组for (int i = 0; i < paiNum; i++) {a[i] = i + 1;}//按照规则排序int st = 0;                     //定义起点int bj = 0;                     //逆推序列数组标号int aj = paiNum;                //加长存放起始标号while(true) {b[bj++] = a[st++];if(a[st + 1] == 0) {b[bj] = a[st];break;}a[aj++] = a[st++];}//由逆推序列得出正确序列for (int i = 0; i < b.length; i++) {c[b[i] - 1] = i + 1;}System.out.println("改错法排出的序列");for (int i : c) {System.out.print(i + " ");}return c;}/** * 逆推法 * 扑克牌排序，三个参数的意思分别为： paiNum牌个数  * hNum每次置地步牌的个数 flag出牌或置底顺序(true为先出牌，false为先置底) * */public static int[] sortByNitui(int paiNum,int hNum,boolean flag) {int[] a = new int[paiNum];  //初始数组int[] b = new int[paiNum];  //正确数组//初始化序列for (int i=0;i<paiNum;i++) {a[i] = paiNum - i;}int ed = paiNum - 1,st = 0;//逆推排序 一张牌置底的时候/*while(ed >= 0) {b[ed] = a[st];if(ed == 0 && l == 0) break;if(ed < paiNum - 1) {int temp =b[paiNum - 1];for(int i = paiNum - 2;i >= ed;i--) {b[i + 1] = b[i];}b[ed] = temp;}st++;ed--;}*///逆推排序 两张牌置底的时候int[] temp = new int[hNum];while(ed >= 0) {b[ed] = a[st];if(ed == 0 && flag) break;if(ed >= paiNum - hNum && ed < paiNum -1 && hNum > 2) {int temphNum = hNum%(st + 1);for(int i = 0;i< temphNum; i++) {temp[i] = b[paiNum - i -1];}for(int i = paiNum - 1 - temphNum;i >= ed;i--) {b[i + temphNum] = b[i];}for(int i =0;i<temphNum;i++) {b[ed + i] = temp[temphNum - i - 1];}}else if(ed < paiNum - hNum) {for(int i = 0;i< hNum; i++) {temp[i] = b[paiNum - i -1];}for(int i = paiNum - 1 - hNum;i >= ed;i--) {b[i + hNum] = b[i];}for(int i =0;i<hNum;i++) {b[ed + i] = temp[hNum - i - 1];}}st++;ed--;}/*System.out.println("\n逆推法排出的序列：");for (int i : b) {System.out.print(i + " ");}*/return b;}/** * 唐粒子的方法 */public static void sortByTang(int num) {int sum, j = 0, k = num;int head = 0, tail = 0;System.out.println();sum = adNum(k);System.out.println(sum);head = 0;tail = k;int[] init = new int[sum];System.out.println("init:" + sum);//初始化for (int i = 0; i < k; i++)init[i] = i + 1;for (int i = 0; i < k; i++) {System.out.print(init[i]);System.out.print(" ");}int[] a = new int[k + 1];while (head != tail) {a[j++] = init[head];if (head + 1 == tail) {//a[j] = init[tail];break;}init[tail++] = init[head + 1];head += 2;}System.out.println();System.out.println("after del:");for (int i = 0; i < j; i++) {System.out.print(a[i]);System.out.print(" ");}int[] out = new int[k];for (int i = 0; i < k; i++)out[a[i] - 1] = i + 1;System.out.println();System.out.println("result:");for (int i = 0; i < k; i++) {System.out.print(out[i]);System.out.print(" ");}}}