打印1到最大的n位數

解法1：按照何老師的思路，這道題用字符串解，需要模擬一個字符串加1的操作，打印的時候注意不能把前面的0打印出來。

bool Increment(char *str) 
{ 
    bool isOverFlow = false; 
    int nTakeOver = 0; 
    int nLength = strlen(str); 
 
    for(int i=nLength-1;i>=0;--i){//在一個循環裡面，對不同的i進行處理  
        int nSum = str[i] - '0' + nTakeOver; 
 
        if(i == nLength - 1)//這種方式編程有特點  
            ++nSum; 
 
        if(nSum >= 10){ 
            str[i] = nSum - 10 + '0'; 
            nTakeOver = 1; 
            if(i == 0) 
                isOverFlow = true; 
        } 
        else{ 
            str[i] = nSum + '0'; 
            break; 
        } 
    } 
    return isOverFlow; 
} 
 
void PrintStr(char* str) 
{ 
    bool flag = true; 
    while(*str){ 
        if(flag&&*str!='0') 
            flag = false; 
        if(!flag||!*(str+1)) 
            cout<<*str; 
        ++str; 
    } 
    cout<<endl; 
} 
 
void Print1ToMax(int n) 
{ 
    char *str = new char[n+1]; 
    memset(str,'0',sizeof(char)*(n+1)); 
    str[n] = '\0'; 
 
    while(!Increment(str)){ 
        PrintStr(str); 
    } 
 
    delete[] str; 
}<SPAN style="FONT-SIZE: 18px"> 
</SPAN> 

bool Increment(char *str)
{
 bool isOverFlow = false;
 int nTakeOver = 0;
 int nLength = strlen(str);

 for(int i=nLength-1;i>=0;--i){//在一個循環裡面，對不同的i進行處理
  int nSum = str[i] - '0' + nTakeOver;

  if(i == nLength - 1)//這種方式編程有特點
   ++nSum;

  if(nSum >= 10){
   str[i] = nSum - 10 + '0';
   nTakeOver = 1;
   if(i == 0)
    isOverFlow = true;
  }
  else{
   str[i] = nSum + '0';
   break;
  }
 }
 return isOverFlow;
}

void PrintStr(char* str)
{
 bool flag = true;
 while(*str){
  if(flag&&*str!='0')
   flag = false;
  if(!flag||!*(str+1))
   cout<<*str;
  ++str;
 }
 cout<<endl;
}

void Print1ToMax(int n)
{
 char *str = new char[n+1];
 memset(str,'0',sizeof(char)*(n+1));
    str[n] = '\0';

 while(!Increment(str)){
  PrintStr(str);
 }

 delete[] str;
}

解法2：其實就是答應0、1、2......7、8、9中n個數的全排列（且各個數可以重復），但是前面的n不要打印出來

void Print1ToMaxRecursivelySub(char *str,int n,int index) 
{ 
    if(index == n){ 
        PrintStr(str); 
        return; 
    } 
    for(int i=0;i<10;++i){  //典型的dfs搜索算法  
        str[index] = i + '0'; 
        ++index; 
        Print1ToMaxRecursivelySub(str,n,index); 
        --index; 
    } 
} 
 
void Print1ToMaxRecursively(int n) 
{ 
    char *result = new char[n+1]; 
 
    memset(result,'\0',sizeof(char)*(n+1)); 
     
    Print1ToMaxRecursivelySub(result,n,0); 
 
    delete[] result; 
} 

void Print1ToMaxRecursivelySub(char *str,int n,int index)
{
 if(index == n){
  PrintStr(str);
  return;
 }
 for(int i=0;i<10;++i){  //典型的dfs搜索算法
  str[index] = i + '0';
  ++index;
  Print1ToMaxRecursivelySub(str,n,index);
  --index;
 }
}

void Print1ToMaxRecursively(int n)
{
    char *result = new char[n+1];

 memset(result,'\0',sizeof(char)*(n+1));
   
 Print1ToMaxRecursivelySub(result,n,0);

 delete[] result;
}

注：上面的代碼與n個組合又不同，同樣用dfs實現n個數的組合

int arr[] = {0,1,2,3,4,5,6,7,8,9};   
int len = 10 , m = 3;   
 
void dfs(int num , vector<int>& vec , int curnum , int index)   
{   
    int i ;   
    if(curnum == num)   
    {   
        for( i = 0; i < vec.size() ; ++i)   
            cout<<vec[i];   
        cout<<endl;   
        return;   
    }   
 
    for( i = index; i < len; ++i)   
    {   
        vec.push_back(arr[i]);   
        dfs(num , vec , curnum + 1 , i + 1);  //i是索引  
        vec.pop_back();   
    }   
} 
int main(void)   
{   
    vector<int>vec;   
    dfs(m , vec , 0 , 0);   
    system("pause"); 
    return 0;   
} 

int arr[] = {0,1,2,3,4,5,6,7,8,9}; 
int len = 10 , m = 3; 

void dfs(int num , vector<int>& vec , int curnum , int index) 
{ 
 int i ; 
 if(curnum == num) 
 { 
  for( i = 0; i < vec.size() ; ++i) 
   cout<<vec[i]; 
  cout<<endl; 
  return; 
 } 

 for( i = index; i < len; ++i) 
 { 
  vec.push_back(arr[i]); 
  dfs(num , vec , curnum + 1 , i + 1);  //i是索引
  vec.pop_back(); 
 } 
}
int main(void) 
{ 
 vector<int>vec; 
 dfs(m , vec , 0 , 0); 
 system("pause");
 return 0; 
}

 組合實現的另一種方案：

nt arr[] = {1,2,3,4,5,6,7,8,9,10};   
int len = 10 , m = 3;   
   
void dfs(int index , int num , vector<int> &vec)   
{   
    int i ;   
    if(index == len+1)   
        return ;   
    if(num == 0)   
    {   
        for( i = 0; i < vec.size() ; ++i)   
            cout<<vec[i]<<" ";   
        cout<<endl;   
        return;   
    }   
    vec.push_back(arr[index]);    // 選取第index個元素    
    dfs(index + 1 , num - 1 , vec);   
    vec.pop_back();               // 不選取第index個元素    
    dfs(index + 1 , num , vec);   
}   
   
int main(void)   
{   
    vector<int>vec;   
    dfs(0 , m , vec);   
    return 0;   
}  

int arr[] = {1,2,3,4,5,6,7,8,9,10}; 
int len = 10 , m = 3; 
 
void dfs(int index , int num , vector<int> &vec) 
{ 
    int i ; 
    if(index == len+1) 
        return ; 
    if(num == 0) 
    { 
        for( i = 0; i < vec.size() ; ++i) 
            cout<<vec[i]<<" "; 
        cout<<endl; 
        return; 
    } 
    vec.push_back(arr[index]);    // 選取第index個元素 
    dfs(index + 1 , num - 1 , vec); 
    vec.pop_back();               // 不選取第index個元素 
    dfs(index + 1 , num , vec); 
} 
 
int main(void) 
{ 
    vector<int>vec; 
    dfs(0 , m , vec); 
    return 0; 
}

 

i