征求一简单算法

Question

做一函数，比如向函数传入一个 10
函数计算出9组各数，每二个一组，必须无重复的组合
向函数传入一个 12 则输出56组等等...//例:如6则输出这样内容,每组必须无重复
//则函数计算出5组各数2个一组无复复的组合1-2,3-4,5-6
2-4,3-5,1-6
3-2,4-6,1-5
4-5,3-1,2-6
5-2,1-4,3-6

Answer 1

楼上的，我觉得是这样的，
输入6，为c（6，2）/3＝5
输入8，为c（8，2）/4＝7
输入10，为c（10，2）/5＝9
输入12，为c（12，2）/6＝11

Answer 2

给搂主一个提议：这是我精心为你设计的一个算法，如果有什么不对的地方，给我发消息！具体算法步骤：
输入num（偶数）时，
用(x,y)模式表示x-y
弄一个邻居表TA，如下是（1,2,3,4,…,i,i+1,…num）的所有二位组合：
p1----> (1,2),(1,3),(1,4)…,(1, num)
p2----> (2,3),(2,4)…(2, num)
p3----> (3,4),…,(3, num)
…
pi---->(i,i+1),…,(i,num)
…
p(num-1)----> (num-1,num)
寻找一组的步骤如下：初始化：定义集合SA,用来存储已经被包含的x,y，初始化SA＝{},
注意：未处理(x1,y1)：表示(x1,y1)没有被尝试地包含在SA中，所谓尝试，是因为即使被包含进去，也可能被回滚掉！第1步，取p1中第一个未处理(1,y1)，SA ={1,y1}；第2步，如果2在SA中，进入第3步，
否则如果p2存在未处理(2,y2)，取p2中第一个未处理(2,y2)，SA =SA+{2,y2}； 
否则如果p2不存在未处理(2,y2)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； 第3步，如果3在SA中，进入第3步，
否则如果p3存在未处理(3,y3)，取p3中第一个未处理(3,y3)，SA =SA+{3,y3}； 
否则如果p3不存在未处理(3,y3)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步；…第i步，如果i在SA中，进入第i+1步，
否则如果pi存在未处理(i,yi)，取pi中第一个未处理(i,yi)，SA =SA+{i,yi}； 
否则如果pi不存在未处理(i,yi)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； …
第num-1步，如果num-1在SA中，进入第num步,
否则如果p(num-1)存在未处理((num-1),y(num-1))，取p(num-1)中第一个未处理((num-1),y(num-1))，SA =SA+{(num-1),y(num-1)}； 
否则如果p(num-1)不存在未处理((num-1),y(num-1))，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步；第num步，如果SA还未全包括{1,2,3,4, …,i,i+1,…num},去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； 
否则，假设SA={x1,y1,x2,y2,…},则从邻居表中删除(x1,y1,(x2,y2),…；然后到初始化重新开始寻找下一组，直到邻居表中没有元素！

Answer 3

更正第3步，如果3在SA中，进入第3步，
否则如果p3存在未处理(3,y3)，取p3中第一个未处理(3,y3)，SA =SA+{3,y3}； 
否则如果p3不存在未处理(3,y3)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步；－－－》第3步，如果3在SA中，进入第4步，
否则如果p3存在未处理(3,y3)，取p3中第一个未处理(3,y3)，SA =SA+{3,y3}； 
否则如果p3不存在未处理(3,y3)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步；

Answer 4

再给你一个例子：
当为6时，
邻居表，
p1----> (1,2),(1,3),(1,4),(1,5),(1,6)
p2----> (2,3),(2,4),(2,5),(2,6)
p3----> (3,4),(3,5),(3,6)
p4----> (4,5),(4,6)
p5----> (5,6)找第1组过程：
第1步，p1取（1，2），SA={1,2}；
第2步, 2在SA中，转下一步；
第3步，p3取 (3，4)，SA={1,2,3,4}；
第4步，4在SA中，转下一步；
第5步，p5取 (5，6)，SA={1,2,3,4,5,6}；
第6步，得到第一组(1,2),(3,4),(5,6），
从邻居表中删除(1,2),(3,4),(5,6），邻居表变为
p1----> (1,3),(1,4),(1,5),(1,6)
p2----> (2,3),(2,4),(2,5),(2,6)
p3----> (3,5),(3,6)
p4----> (4,5),(4,6)找第2组过程：
第1步，p1取（1，3），SA={1,3}；
第2步, p2取 (2，4)，SA={1,3,2,4}；
第3步，3在SA中，转下一步；
第4步，4在SA中，转下一步；
第5步，p5不存在未处理(5,y5)，去掉最后加入SA的两个数,SA={1,3}；然后返回到最后加入元素到SA的第2步,
第2步, p2取 (2，5)，SA={1,3,2,5}；
第3步，3在SA中，转下一步；
第4步，p2取 (4，6), SA={1,3,2,5,4,6}；
第5步，5在SA中，转下一步
第6步，得到第二组(1,3),(2,5),(4,6），
从邻居表中删除(1,3),(2,5),(4,6），邻居表变为
p1----> (1,4),(1,5),(1,6)
p2----> (2,3),(2,4)(2,6)
p3----> (3,5),(3,6)
p4----> (4,5)找第3组过程：
…
找第4组过程：
…
找第5组过程：
…
p1----> (1,6)
p2----> (2,3)
p3---->
p4----> (4,5)可以找到5组为
(1,2),(3,4),(5,6）
(1,3),(2,5),(4,6）
(1,4),(2,6),(3,5）
(1,5),(2,4),(3,6）
(1,6),(2,3),(4,5）结果正确吧？

Answer 5

to handwolf(青松崖):其实最后还是求组合问题。
我没有看你写的东东，现在晚了，等下我到了床上睡觉的时候去想算了。其实按你的想法，就是输入一个偶数，得到偶数-1组。只不过楼主没有说清楚。而我想搞清楚而已。

Answer 6

#include"stdio.h"void PrintCom(int* pArray,int nCount)
{
if(pArray==NULL || nCount<=1)
{
return ;
} int nTotal ;
int nCursor1 = 0 ;
int nCursor2 = 1 ; for(nTotal=nCursor1=0; nCursor1<nCursor2; ++nCursor1)
{
for(nCursor2=nCursor1+1; nCursor2<nCount; ++nCursor2)
{
printf("(%d,%d)\r\n",pArray[nCursor1],pArray[nCursor2]) ;
++nTotal ;
}
}
printf("Total = %d \r\n",nTotal) ;
}void main()
{
int Array[] = {1,2,3,4,5,6,7};
PrintCom(Array,sizeof(Array)/sizeof(int)) ;
}

Answer 7

是的， handwolf(青松崖) 说的对，每组无重复，而且2个一组
如果输入6就是6/2=3 ，每行输出3对内容，共输出1+2+3+4+5 = 15行内容
如果输入10就是10/2=5,每行输出5对内容，共输出1+2+3+4...= 45行内容
如果输入12就是12/2=6,每行输出6对内容，共输出1+2+3...  = 66行内容我昨天想了一天也没想到一个有规律的算法，大家帮忙想想看能不能想到？

Answer 8

不是15行啦，是15对，不过要是数据多的话，10 个数以上的，后期不是要返回好几层嘛？==>第5步，p5不存在未处理(5,y5)，去掉最后加入SA的两个数,SA={1,3}；然后返回到最后加入元素到SA的第2步,   想想就头疼我正在写这个程序，需要设置很多标志，中途，整得我脑袋都大了
后期算法简直无法形容了对了楼上的，有时间帮忙写写看啊，看是不是代码真像我想像中的那么难？

Answer 9

//浪费了一上午时间，只写到标志返回上次结果这里，正琢磨怎么写这个标志呢，挺复杂的感觉，想了半天！也没想出个之所以然...#include "iostream.h"const UINT BUFFERSIZE = 65535;  //缓冲区总大小
const UINT LINEBUFFER = 512; //每行缓冲区总大小
const UINT TABLESIZE  = 10; //表的行数和列数，建立二维数组char ga_table[TABLESIZE][TABLESIZE];void ReArray(int num)
{
char buff[BUFFERSIZE] = ""; //用于记录全部已输出的内容，用于比较一组数字
char buff1[LINEBUFFER] = ""; //用于记录此行已输出的内容,用于比较单个数字
char temp_char[16]; //存储临时的一组数据
//char p1[2]="",p2; //用于将整型拆分后与一组数据分别对比
int i=0,k=0;
for(k=0;k<num;k++)
{
for(i=0;i<num;i++)
{
memset(temp_char,0x00,16);
temp_char[0] = ga_table[i][k]; //得到一组字符：12 or 13 or 23
itoa(temp_char[0],temp_char,10); //将自己从整型转成字符型
if(!strrchr(buff1,temp_char[0]) && !strrchr(buff1,temp_char[1]))
{
strcat(buff1,temp_char);
strcat(buff1,","); //将结果储存到单行数组里用于查找
} //----------------在此设置标志，返回上次查找错误的地方重新计算---------------- }
strcat(buff,buff1); //将单行数的n组数据存到总结果集里 cout << buff1 << endl;
memset(buff1,0x00,LINEBUFFER);
}
}void CountArray(int num)
{
int i,k;
memset(ga_table,0x00,sizeof(ga_table));
for(i=1;i<num;i++)
{
for(k=1;k<num;k++)
{
if(i+k<=num)
ga_table[i-1][k-1] = i*10+i+k; //横向第一组对应 12,13,14,15,16
} //横向第二组对应 23,24,25,26
//横向第二组对应 34,35,36
//横向第二组对应 45,46
//横向第二组对应 56
} for(i=0;i<num;i++)
{
for(k=0;k<num;k++)
{
if((int)ga_table[i][k])
cout << (int)ga_table[i][k] << "," ;
//if(0 == k%3)cout << endl;
}
cout << endl;
} //输出表中所有数据 ReArray(num);
}int main(void)
{
int a;
while(1)
{
cin >> a;
CountArray(a); cin.clear();
cin.ignore();
} return 0;
}

Answer 10

楼主，最好用stl实现
有时间的话，我给你写一个，不过你就错过了一个锻炼的机会！
这可不是csdn论坛的目的

Answer 11

可是，我对STL真的是一窍不通呀~ 一点都没接处过！ ；~~（

Answer 12

我感觉标志那里好像得做一个递归的算法，用于返回行结果的undo

Answer 13

楼主，写得很辛苦呀，终于搞定了！！！
下面是运行结果预览：Please input a number(>0):12
邻居表：
(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)(1,8)(1,9)(1,10)(1,11)(1,12)
(2,3)(2,4)(2,5)(2,6)(2,7)(2,8)(2,9)(2,10)(2,11)(2,12)
(3,4)(3,5)(3,6)(3,7)(3,8)(3,9)(3,10)(3,11)(3,12)
(4,5)(4,6)(4,7)(4,8)(4,9)(4,10)(4,11)(4,12)
(5,6)(5,7)(5,8)(5,9)(5,10)(5,11)(5,12)
(6,7)(6,8)(6,9)(6,10)(6,11)(6,12)
(7,8)(7,9)(7,10)(7,11)(7,12)
(8,9)(8,10)(8,11)(8,12)
(9,10)(9,11)(9,12)
(10,11)(10,12)
(11,12)结果之一:
(1,2)(3,4)(5,6)(7,8)(9,10)(11,12)
(1,3)(2,4)(5,7)(6,8)(9,11)(10,12)
(1,4)(2,3)(5,8)(6,7)(9,12)(10,11)
(1,5)(2,6)(3,9)(4,10)(7,11)(8,12)
(1,6)(2,5)(3,10)(4,9)(7,12)(8,11)
(1,7)(2,8)(3,11)(4,12)(5,9)(6,10)
(1,8)(2,7)(3,12)(4,11)(5,10)(6,9)
(1,9)(2,10)(3,7)(4,8)(5,11)(6,12)
(1,10)(2,9)(3,8)(4,7)(5,12)(6,11)
(1,11)(2,12)(3,5)(4,6)(7,9)(8,10)
(1,12)(2,11)(3,6)(4,5)(7,10)(8,9)
Press any key to continue下面是源代码：
//引用////////////////////////////////////////////////////////////////////
#include <list>
#include <iostream>
using namespace std ;
////////////////////////////////////////////////////////////////////////类定义(start)///////////////////////////////////////////////
//(x,y)模式
class CPair{
public:
int x;
int y;
int iMode;//iMode=0--未处理
          //iMode=1--处理过
          //iMode=2--已删除
public:
CPair():x(0),y(0),iMode(0){ };
CPair(const CPair& cp)
{
x = cp.x;
y = cp.y;
iMode = cp.iMode;
};
public:
CPair& operator=(CPair& cp)
{
x = cp.x;
y = cp.y;
iMode = cp.iMode;
return *this;
}
void Print()
{
cout<<"("<<x<<","<<y<<")";
};
};typedef list<int> LISTINT;
typedef list<CPair> LISTPAIR;
typedef list<CPair*> LIST_PPAIR;
//结构定义(end)/////////////////////////////////////////////////函数声明(start)///////////////////////////////////////////////
void InitNBTable(int iNum);
void FreeNBTable();
bool ExistInSA(int iTeamNum);
void ErazeTempMode();
void GetOneLine();
void GetAllLine(int iNum);
//函数声明(end)/////////////////////////////////////////////////全局变量(start)///////////////////////////////////////////////
LISTPAIR* gl_pNBTanle;//存储邻居表
int       gl_iTeamCount;//球队数
LIST_PPAIR  gl_lstPair_SA; //集合SA
LISTINT   gl_lstInt_Steps;//记录向SA加入内容的步骤序列
//存储SA
//全局变量(end)/////////////////////////////////////////////////程序入口(start)/////////////////////////////////////////////
void main()
{
   int iNum=0;
   cout<<"Please input a number(>0):";
   cin>>iNum;
   GetAllLine(iNum);
}
//程序入口(end)///////////////////////////////////////////////函数定义(start)/////////////////////////////////////////////
//InitNBTable
//初始化邻居表
//参数iNum：输入的球队个数（如果是奇数 则为 奇数+1）
void InitNBTable(int iNum)
{
if(iNum <= 0)
return; if(iNum % 2 != 0)
++iNum;//变成偶数，最后一个数代表空球队！
    gl_iTeamCount = iNum; gl_pNBTanle = new LISTPAIR[gl_iTeamCount-1];
CPair cpInfo;
cout<<"邻居表："<<endl;
for(int i = 1; i < gl_iTeamCount; ++i){
for(int j = i+1; j < gl_iTeamCount + 1; ++j){
cpInfo.x = i;
cpInfo.y = j;
cpInfo.iMode = 0;
cpInfo.Print();
gl_pNBTanle[i-1].push_back(cpInfo); 
}
cout<<endl;
}
cout<<endl;
}//FreeNBTable
//释放邻居表占用的空间
void FreeNBTable()
{
if(gl_pNBTanle == NULL)
return; for(int i = 0; i < gl_iTeamCount-1; ++i){
gl_pNBTanle[i].clear();
} delete[] gl_pNBTanle;
}//查找球队iTeamNum是否已经在SA中
bool ExistInSA(int iTeamNum)
{
LIST_PPAIR::iterator iter;
for (iter = gl_lstPair_SA.begin(); iter != gl_lstPair_SA.end(); ++iter){
CPair* pInfo = *iter;
if(pInfo->x == iTeamNum || pInfo->y == iTeamNum)
return true;
} return false;
}
//将用所有尝试标志恢复为未尝试
void ErazeTempMode()
{
LISTPAIR::iterator iter;
for(int i = 0; i < gl_iTeamCount-1; ++i){
//恢复尝试标志为未尝试
for (iter = gl_pNBTanle[i].begin(); iter != gl_pNBTanle[i].end(); ++iter){
CPair& cpInfo = *iter;
if(cpInfo.iMode == 1){//尝试
cpInfo.iMode = 0; //未尝试
}
}
}
}//得到一行
void GetOneLine()
{
LISTPAIR::iterator iter;
gl_lstInt_Steps.clear();
gl_lstPair_SA.clear();
ErazeTempMode(); for(int i = 1; i < gl_iTeamCount;){
if(ExistInSA(i) == true)//i是否在SA中
{
//下一步
++i;
continue;
}

//寻找第一个未处理的一对
for (iter = gl_pNBTanle[i-1].begin(); iter != gl_pNBTanle[i-1].end(); ++iter){
CPair* pInfo = &(*iter);
if(pInfo->iMode == 0 && ExistInSA(pInfo->y) == false){//存在未处理的一对
pInfo->iMode = 1; //设置标志
gl_lstPair_SA.push_back(pInfo);
gl_lstInt_Steps.push_back(i);
break;
}
}
if(iter == gl_pNBTanle[i-1].end()){//不存在未处理的一对,回滚
//恢复尝试标志为未尝试
for (iter = gl_pNBTanle[i-1].begin(); iter != gl_pNBTanle[i-1].end(); ++iter){
CPair& cpInfo = *iter;
if(cpInfo.iMode == 1){//尝试
cpInfo.iMode = 0; //未尝试
}
}

i = gl_lstInt_Steps.back();//回滚
gl_lstInt_Steps.pop_back();
gl_lstPair_SA.pop_back();//去掉最后加入SA的两个数
continue;
}

//下一步
++i;
}
for (LIST_PPAIR::iterator iter2 = gl_lstPair_SA.begin(); 
    iter2 != gl_lstPair_SA.end(); ++iter2)
{
CPair* pInfo = *iter2;
pInfo->iMode = 2;
pInfo->Print();
}

cout<<endl;
}//得到所有行
void GetAllLine(int iNum)
{
if(iNum <= 0){
cout<<"Please in put a number bigger than 0!"<<endl;
return;
}
InitNBTable(iNum);
cout<<"结果之一:"<<endl;
for(int i = 0; i < gl_iTeamCount-1; i++){
GetOneLine();
}
FreeNBTable();
}
//函数定义(end)/////////////////////////////////////////////