Wednesday, March 23, 2011

"K-arian" chains


  • I don't know the translation for "K-arias", but the problem is to build all the combinations possible of length n, having the digits from 0 to k-1. Here's the code based on mr.Zaragoza's page


[sourcecode language="cpp"]
#include <iostream>
#define BINARIA 2
#define KARIA 3
using namespace std;
int A[BINARIA],B[KARIA];
void procesa_b(int* A){
for(int i=0; i<BINARIA; i++)cout<<A[i]<<" ";
cout<<endl;
}
void procesa_k(int* A){
for(int i=0; i<KARIA; i++)cout<<A[i]<<" ";
cout<<endl;
}
void binario( int m){
if(m == -1) procesa_b(A);
else{
A[m] = 0; binario(m-1);
A[m] = 1; binario(m-1);
}
}
void cadena(int m,int k){
if(m==-1)procesa_k(B);
else{
for(int j=0; j<k; j++){
B[m] = j;
cadena(m-1,k);
}
}
}
int main(){
cout<<"binario: "<<endl;
binario(BINARIA);
cout<<"cadena: "<<endl;
cadena(KARIA,KARIA);
return 0;
}

[/sourcecode]

  • The issue I'm having is that "binario" is calling "procesa" exactly twice for each chain found (and makes sense since we're making two recursive calls) when it's supposed to be calling it only once.



  • Solved:  cero based array ----> decrease m by 1 in comparisons (which I intuitively did) and when calling the recursive functions (the missing part).


[sourcecode language="cpp"]
#include <iostream>
#define BINARIA 2
#define KARIA 3
using namespace std;
int A[BINARIA],B[KARIA];
void procesa_b(int* A){
for(int i=0; i<BINARIA; i++)cout<<A[i]<<" ";
cout<<endl;
}
void procesa_k(int* A){
for(int i=0; i<KARIA; i++)cout<<A[i]<<" ";
cout<<endl;
}
void binario( int m){
if(m == -1) procesa_b(A);
else{
A[m] = 0; binario(m-1);
A[m] = 1; binario(m-1);
}
}
void cadena(int m,int k){
if(m==-1)procesa_k(B);
else{
for(int j=0; j<k; j++){
B[m] = j;
cadena(m-1,k);
}
}
}
int main(){
cout<<"binario: "<<endl;
binario(BINARIA-1);
cout<<"cadena: "<<endl;
cadena(KARIA-1,KARIA);
return 0;
}
[/sourcecode]

No comments:

Post a Comment