面接訓練文字列の組合せ
2622 ワード
タイトル:文字列を入力し、その文字列のすべての組合せを出力します.例えば、abcが入力されると、その組み合わせはa、b、c、ab、ac、bc、abcである.
最初は私の考えは再帰だったが、具体的にどうするかは考えられなかった.
后ろで涛兄日志の中の1人のネットユーザーの返事を见て、文字列を01と见て数字の列を构成して、1はアルファベットがあって、このように1から2^nの数字の中でどの位が1で、文字列に対応します
コードが簡単:
参考海濤の再帰解法
大波のブログを見て目の前が明るくなってよかったです.考えはこうだ
長さnの文字列からm文字を取り出します.どうやって取りますか.1最初の文字を取り、残りのn-1文字の列にm-1文字を取ります.
2最初の文字を取らず、残りのn文字列からm文字を削除
もちろん再帰的な戻りには条件が必要であり,文字列が終了したり,長さnが取得されたりしたときに終了する.
コードは次のとおりです.
最初は私の考えは再帰だったが、具体的にどうするかは考えられなかった.
后ろで涛兄日志の中の1人のネットユーザーの返事を见て、文字列を01と见て数字の列を构成して、1はアルファベットがあって、このように1から2^nの数字の中でどの位が1で、文字列に対応します
コードが簡単:
#include "stdio.h"
#include "math.h"
#include "string.h"
int main()
{
int len ;
int i,j;
int number;
char str[1024];
scanf("%s",&str);
len = strlen(str);
number = pow(2,len);
for(i=1;i<number;i++)
{
for(j=0;j<len;j++)
{
if((i>>j)&1)
{
printf("%c",str[j]);
}
}
printf(" ");
}
return 0;
}
参考海濤の再帰解法
大波のブログを見て目の前が明るくなってよかったです.考えはこうだ
長さnの文字列からm文字を取り出します.どうやって取りますか.1最初の文字を取り、残りのn-1文字の列にm-1文字を取ります.
2最初の文字を取らず、残りのn文字列からm文字を削除
もちろん再帰的な戻りには条件が必要であり,文字列が終了したり,長さnが取得されたりしたときに終了する.
コードは次のとおりです.
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#define MAX 1024
typedef struct node{
char data;
struct node *next;
}MyNode;
typedef struct queue{
MyNode *tail;
MyNode *top;
int size;
}lineQueue;
void push( lineQueue *q,char data)
{
MyNode *p = ( MyNode *)malloc(sizeof( MyNode));
p->data = data;
p->next = NULL;
if(q->tail != NULL)
{
(q->tail)->next = p;
}
q->tail = p;
if(q->top == NULL)
{
q->top = p;
}
q->size +=1;
}
void pop( lineQueue *q,char *data)
{
MyNode *p;
if(q->top == NULL)
return;
p = q->top;
if(q->top == q->tail) /* , , */
{
q->tail = NULL;
}
*data = q->top->data;
q->top = q->top->next;
free(p);
q->size-=1;
}
void initQueue(lineQueue **q)
{
if(*q == NULL)
{
*q = (lineQueue *)malloc(sizeof(lineQueue));
}
(*q)->top = NULL;
(*q)->tail = NULL;
(*q)->size = 0;
}
void traverse(lineQueue *q)
{
MyNode *p = NULL;
p = q->top;
while(p!=NULL)
{
printf("%c",p->data);
p= p->next;
}
}
void combineLine(char *str,int num,lineQueue *q)
{
int i =0;
char data;
if(num == 0)
{
traverse(q);
printf(" ");
return;
}
if(*str == '\0')
{
return;
}
push(q,*str);
combineLine(str+1,num-1,q);
pop(q,&data);
combineLine(str+1,num,q);
}
void combine(char *str,lineQueue *q)
{
int i = 0;
int len = strlen(str);
for(i=1;i<=len;i++)
{
combineLine(str,i,q);
}
}
int main()
{
lineQueue *q=NULL;
int num=5;
int i;
char str[1024];
initQueue(&q);
scanf("%s",str);
combine(str,q);
return 0;
}