12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
我的程序如下：
/*问题描述: 12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种? */#include<stdio.h>#include<assert.h>#define N 12#define M 6void form_two_lines(int [],int ,int );int valid(int [],int );int finish(int [],int );void output(int []);static int x[N];int main(){ int i; int array[N]={170,171,172,173,174,175,176,177,178,179,180,181}; //身高cm i=0; while(i<N){ //初始化x[] x[i]=-1; i++; } form_two_lines(array,N,0); //生成两个对列 return 0;}//将数组array[]排成两排void form_two_lines(int array[],int n,int i){ //进入该函数前，已经有i个人站好，且正确 if(finish(x,i)){ output(array); } else{ for(int k=0;k<=1;k++){ x[i]=k; //x[i]==0代表第i个人站在第0排，否则第1排 if(valid(array,i)) form_two_lines(array,n,i+1); }//for }//else}//判断目前排队是否正确int valid(int array[],int n){ int i,j,k; int zero[M],one[M]; i=0; while(i<M){ //initial [] zero[i]=one[i]=0; i++; } i=j=k=0; while(i<=n){ if(x[i]==0) zero[j++]=array[i]; else if(x[i]==1) one[k++]=array[k]; i++; } k = j>k ? k : j; //去较小值 while(i<k){ if(zero[i]>one[i]||one[i]) return 0; i++; } return 1;}//某一排是否排满6个，若已有6个则结束递归int finish(int y[],int n){ int i=0; int zero,one; zero=one=0; while(i<n){ if(y[i]==1) one++; else if(y[i]==0) zero++; } if(one==6||zero==6) return 1; return 0;}//输出两排身高void output(int array[]){ int i,m,n; int zero[M],one[M]; i=m=n=0; while(i<N){ if(x[i]){ one[n]=array[i]; n++; } else{ zero[m]=array[i]; m++; } i++; } i=0; while(i<M){ printf("%d ",zero[i]); i++; } printf("\n"); i=0; while(i<M){ printf("%d ",one[i]); }}#include <stdio.h>#include <vector>#define LIST_NUM 6#define ROW_NUM 2int _tall[LIST_NUM*ROW_NUM];int _count=0;typedef std::vector<int> TallList;int GetPossibleTall(int c_tall[ROW_NUM][LIST_NUM],int row,int list,TallList* talllist);bool EnableTall(int c_tall[ROW_NUM][LIST_NUM],int row,int list,int tall);bool Try(int c_tall[ROW_NUM][LIST_NUM],int num);void main(){ for (int i=0;i<LIST_NUM*ROW_NUM;i++) { _tall[i]=i+160; } int current_tall[ROW_NUM][LIST_NUM]; memset(current_tall,0,ROW_NUM*LIST_NUM*sizeof(int)); Try(current_tall,0); printf("总计%d种方案.....",_count);}bool Try(int c_tall[ROW_NUM][LIST_NUM],int num){ int row=num/LIST_NUM; int list=num-row*LIST_NUM; TallList tlist; int tnum=GetPossibleTall(c_tall,row,list,&tlist); if (!tnum) { return false; } for (int k=0;k<tnum;k++) { int new_tall[ROW_NUM][LIST_NUM]; memcpy(new_tall,c_tall,ROW_NUM*LIST_NUM*sizeof(int)); new_tall[row][list]=tlist.at(k); if (num<ROW_NUM*LIST_NUM-1) { Try(new_tall,num+1); } else { _count++; printf("方案%d：\t",_count); for (int i=0;i<ROW_NUM;i++) { for (int j=0;j<LIST_NUM;j++) { printf("%d\t",new_tall[i][j]); } printf("\n\t\t"); } printf("\n"); } } return true;}int GetPossibleTall(int c_tall[ROW_NUM][LIST_NUM],int row,int list,TallList* talllist){ talllist->clear(); if (c_tall[row][list]) { return 0; } int shorter=row+list+row*list; int taller=(ROW_NUM-row)*(LIST_NUM-list)-1; for (int i=shorter;i<LIST_NUM*ROW_NUM-taller;i++) { int ptall=_tall[i]; if (EnableTall(c_tall,row,list,ptall)) { talllist->push_back(ptall); } } return talllist->size();}bool EnableTall(int c_tall[ROW_NUM][LIST_NUM],int row,int list,int tall){ for (int r=0;r<ROW_NUM;r++) { for (int l=0;l<LIST_NUM;l++) { int ctall=c_tall[r][l]; if (!ctall) { continue; } if (tall==ctall) { return false; } else if ((list>=l)&&(row>=r)&&(tall<ctall)) { return false; } else if ((list<=l)&&(row<=r)&&(tall>ctall)) { return false; } } } return true;}
[解决办法]
只看第一排，范围是从1，2，3，4，5，6－1，3，5，7，9，11，写个函数求下一个序列即可
[解决办法]
#include <stdio.h>#include <stdlib.h>int person[6] = {1,2,3,4,5,6};int count = 0;int print_solution(int *p){ int target[6] = {2,2,2,2,2,12}; int i = 0; int j = 0; for (i=0; i<5; i++) { for (j=0; j<6; j++) { if (i==0&&((target[i]<person[i])||(target[i]==person[j]))) { target[i]++; if (target[i]==12) { return 0; } j = 0; } else if ((target[i]<person[i])|| (target[i]==person[j])|| (target[i]<=target[i-1])) { target[i]++; if (target[i]==12) { return 0; } j = 0; } } } count++; printf("============================\n"); printf("Number.%d solution is: \n",count); for (i=0; i<6; i++) { printf("%d ",*(p+i)); } printf("\n"); for (i=0; i<6; i++) { printf("%d ",target[i]); } printf("\n"); return 1;}void recursion(int *p, int level, int value){ if (level==6) { person[level-1] = 2; while ((person[level-1]<=value)&&(person[level-1]<12)) { person[level-1]++; } while ((person[level-1]>value)&&(person[level-1]<12)) { print_solution(p); person[level-1]++; } return; } int i = level; person[level-1] = 2; for (; i<level+6; i++) { while (person[level-1]<=value) { person[level-1]++; } recursion(p,level+1,person[level-1]); person[level-1]++; }}void main(){ recursion(person,2,1);}
[解决办法]
按6楼方案写了个程序，不过只输出了第一行，结果132
#include<stdio.h>int end[5]={3,5,7,9,11};int begin[5]={2,3,4,5,6};bool GetNextValue(int * pData,int pos){ pData[pos]++; if (pData[pos] <= end[pos]) return true; int nNext = pos -1; while (nNext>=0) { pData[nNext]++; if (pData[nNext]<=end[nNext]) { for (int i = nNext;i<pos;i++) pData[i+1]=pData[i]+1; return true ; } else --nNext; } return false;}int main(){ printf ("1,%d,%d,%d,%d,%d \n",begin[0],begin[1],begin[2],begin[3],begin[4],begin[5]); int nTotal =1; while (1) { if (!GetNextValue(begin,4)) break; printf ("1,%d,%d,%d,%d,%d \n",begin[0],begin[1],begin[2],begin[3],begin[4],begin[5]); nTotal++; } printf ("nTotal =%d \n",nTotal); getchar();return 0;}
[解决办法]
[Quote=引用:]
还有的我也有点糊涂，k=j>k ? k:j; 这个是去较大值还是去较小值？
还有 while(i<k){if(zero[i]>one[i]||one[i]) 这个||one[i]是说第one排上不能有人？
还有我要去找找书，看一下静态全局变量和全局变量的区别。
还有头文件<assert.h>是。。。。。。
[解决办法]
假设按升高排序后编号为1到12最矮的是1最高的是12
第一排第一个必须是最矮的；
第二排最后一个必须是最高的；
以下只座位号：
第二排07 08 09 10 11 12
第一排01 02 03 04 05 06
01位置只能最矮的站1，12位置只能最高的站12
06位置最小放6因为01到06是递增的
所以06号位置可以穷举6到11的人。选出A
07位置最大放置7因为07-12是递增的。
所以07好位置可以穷举2到7的人。选出B （A不等于B）
第二排[A] 08 09 10 11 [12]
第一排[1] 02 03 04 05 [B]
[]内表示站好了的人编号，没加[]表示座位号而已没有人占
站好4个人了剩下好有8个人，
然后此时02位置必须放置8人中最矮的，11位置必须放置最高的。
再按上述步骤穷举08 和 05 号位置的人选。
剩下4个人。
03放4人中最矮的，10放最高的，04和09可互换。
可以看出每次是放置好最高最矮的，然后穷举最矮的上面的位置和最高的下面的位置
重复上述步骤即可产生一个序列，
最后只要加一个判断第二排是否都大于第一排，并且1,2两排是否有序。