求个算法
有一个可变二维数组 a[m][n];
例如:
a[0]={1,2,3,4,5,6};
a[1]={1,2,3,4,5};
a[2]={1,2,3,4};
a[3]={1,2,3,4,5,6,7};
a[i]={x,y,z};
我需要遍历这个数组，并且规则如下：
a[0][0],a[1][0],a[2][0],a[3][0],a[i][0]
a[0][1],a[1][0],a[2][0],a[3][0],a[i][0]
a[0][2],a[1][0],a[2][0],a[3][0],a[i][0]
a[0][n-1],a[1][0],a[2][0],a[3][0],a[i][0]
a[0][0],a[1][1],a[2][0],a[3][0],a[i][0]
a[0][0],a[1][n-1],a[2][0],a[3][0],a[i][0]
即 每次从每个数组中选一个值出来与其他数组的值做匹配成一组数据。
突然脑子就短路了，没想出这个循环要怎么写。
[解决办法]
能把那个遍历规则用文字描述一下么？
[解决办法]
//下面主要是用了递归，一旦满足条件，使前一位增1
#include <vector>
#include <iostream>
using namespace std;
int check(int curpos, vector<int> &pos, vector<vector<int> > a);
int main()
{
vector<vector<int> > a;
vector<int> suba;
suba.push_back(1);
suba.push_back(2);
a.push_back(suba);
vector<int> subb;
subb.push_back(11);
subb.push_back(12);
subb.push_back(13);
a.push_back(subb);
vector<int> subc;
subc.push_back(21);
subc.push_back(22);
subc.push_back(23);
subc.push_back(24);
a.push_back(subc);
vector<int> pos;
pos.resize(a.size());
for(int i=0; i<(int)pos.size(); i++)
{
pos[i]=0;
}
for(int i=0; i<(int)a.size();)
{
cout<<a[i][pos[i]]<<",";
i++;
if(i==a.size())
{
cout<<endl;
int ret = check(i-1,pos, a);
if(ret == 0)
break;
i=0;
}
}
}
int check(int curpos, vector<int> &pos, vector<vector<int> > a)
{
pos[curpos]++;
if(curpos==0)
{
if(pos[0]>=a[0].size())
{return 0;}
}
if(pos[curpos]>=a[curpos].size())
{
pos[curpos] = 0;
int ret = check(curpos-1,pos, a);
if(ret==0)
return 0;
}
return 1;
}
[解决办法]
[解决办法]
就是一个求排列组合的问题
[解决办法]
用一个 数组,len[m]记录a[m]的每一个维度的长度.
一个数组保存参数 arg[m];
然后假设你那个其他函数是 f(arg[],m)这样调用
//m是维数,n表示已经构造了n个数据.开始是 1;
void fun(int **arr,int *len,int* arg,int m,int n=1)
{
if(n==m)
{
f(arg,m);
return ;
}
for(int i=0;i<len[n];i++)
{
int temp=arr[n];
arg[n]=arr[n][i];
fun(arr,len,arg,m,n+1);
arr[n]=temp;//恢复.
}
}
[解决办法]
这样的问题用递归很容易解决：
- C/C++ code
#include<iostream>#include<vector>#include<stack>using namespace std;void setVector(vector<vector<int> > &a){ // 这个只是用来构建测试数据的，别当真了。 vector<int> a1; int an[]={6,5,4,7,3}; for (int i=0;i<5;++i) { a.push_back(a1); for (int j=0;j<an[i];++j) a[i].push_back(j+1); }}void output(vector<vector<int> > &a,int c){ static int ai[100]; if (c<0) { for (int i=0;i<a.size();++i) cout<<ai[i]<<" "; cout<<endl; } else { for (int i=0;i<a[c].size();++i) { ai[c]=a[c][i]; output(a,c-1); } }}int main(){ vector<vector<int> > a; setVector(a); // 构建数组，这个部分我就偷懒了哈 output(a,a.size()-1); // 递归输出 return 0;}
[解决办法]
再发一遍：
- C/C++ code
arr二维数组。 len 各维度长度。 arg 生成的参数 m，总维度数目。 k，构造arg[k].void fun(int **arr,int *len,int *arg,int m,int k=0){if(k+1==m){for(int i=0;i<m;i++) printf("%d ",arg[i]);puts("");}for(int j=0;j<len[k];j++){int t=arg[k];arg[k]=arr[k][i];fun(arr,len,arg,m,k+1);arg[k]=t;}}
[解决办法]