让我想了2个钟头的迅雷笔试算法题
对一个有空格的字符串"1111 0000"，现在做以下规定：
1. 1只能往右移动，0只能往左移动
2. 空格两边的1和0可以移动进入空格
3. 1可以跳过0进入空格,0可以跳过1进入空格
编程，用最少的步骤，将字符串移动变为"0000 1111"，并打印出移动过程。
请各位大侠赐教，真不知道这算法该如何写
[解决办法]
我写的罗里啰嗦。。。。
#include <stdio.h>void move_char(char *s, char *t);void fun(char *str, int j);int main(){ char str[] = "1111 0000"; int i; for(i = 0; i < 4; i++) { fun(str, i); move_char(&str[i+5], &str[i]); } fun(str, 4); printf("%s\n", str); return 0;}void move_char(char *s, char*t){ char temp; temp = *s; *s = *t; *t = temp; if (*t == '1') { printf("[%c] move to [%c]\n", *t, *s); } else { printf("[%c] form 1111 jump to [%c]\n", *t, *s); }}void fun(char *str, int j){ while(str[j] != ' ') { int i; for(i = 0; str[i] != ' '; i++) { ; } move_char(&str[i-1], &str[i]); }}
[解决办法]
可以采用下面的代码实现。你可以尝试一下：
[code=C/C++][/code]
#include<stdio.h>
#include<string.h>
void MoveChar(char *ch,int i,int pos)
{
char temp;
temp=ch[i];
ch[i]=ch[pos];
ch[pos]=temp;
}
void StrPrint(char *ch)
{
printf("%s\n",ch);
}
int main()
{
char str[] = "11111 00000";
int i=0;
int iLen=strlen(str);
int iNullPos;
StrPrint(str);
for(i = 0; i <iLen; i++)
{
if(' '==str[i])
{ iNullPos=i;
break;
}
else
{
continue;
}
}
MoveChar(str,0,iNullPos);
StrPrint(str);
int j=iLen-1;
for(i=0;i<iNullPos;i++)
{
char temp;
MoveChar(str,i,j);
StrPrint(str);
if(i!=j)
{
MoveChar(str,i+1,j);
StrPrint(str);
}
else
{
break;
}
j--;
}
return 0;
}
[解决办法]
#include <iostream>
using namespace std;
char question[9] = {'1','1','1','1',' ','0','0','0','0'};
char result[9] = {'0','0','0','0',' ','1','1','1','1'};
struct statenode
{
char state[9];
statenode *next;
};
statenode *stack = NULL;
int search(int start, int type)
{
if( type == 2 )
{
if( question[start] == '1')
{
if( question[start+1] == ' ' )
return 1;
}
else if( question[start] == ' ' )
{
if( question[start+1] == '0' )
return 1;
}
}
else
{
if( question[start] == '1')
{
if( question[start+1] == '0' && question[start+2] == ' ')
return 1;
}
else if( question[start] == ' ' )
{
if( question[start+1] == '1' && question[start+2] == '0' )
return 1;
}
}
return 0;
}
void move(int start, int type)
{
char tmp;
if( type == 2 )
{
tmp = question[start];
question[start] = question[start+1];
question[start+1] = tmp;
}
else
{
tmp = question[start];
question[start] = question[start+2];
question[start+2] = tmp;
}
}
void savestate()
{
statenode *tmp;
tmp = new statenode;
strcpy( tmp->state, question);
tmp->next = stack;
stack = tmp;
}
void loadstate()
{
statenode *tmp;
strcpy(question, stack->state);
tmp = stack;
stack = stack->next;
delete tmp;
}
int statecmp()
{
statenode *tmp = stack;
while(tmp!=NULL)
{
if( 0 == strcmp( question, (const char *)&(tmp->state) ) )
return 0;
tmp = tmp->next;
}
return 1;
}
void answer()
{
int i,type;
static int step = 0;
for(i=0; i <8; i++)
{
for(type=2; type <4; type++)
{
if( (i+type) <=9 )
{
if( search(i,type) )
{
savestate();
move(i,type);
step++;
if( !strcmp(question, result) )
{
cout < <step < <endl;
statenode *out = stack;
while(out!=NULL)
{
cout < <out->state < <endl;
out = out->next;
}
}
if( statecmp() )
{
answer();
loadstate();
step--;
}
else
{
loadstate();
step--;
}
}
}
}
}
}
void main()
{
answer();
system("PAUSE");
}
void printStep( int step, char *buf)
{
printf("step : %d , [%s]\r\n",step,buf);
}
int main(int argc, char **argv)
{
int i = 0;
int l = 0;
int r = 8;
char buf[10] = "1111 0000";
buf[0] = ' ';
buf[4] = '1';
printStep(1,buf);
for( i = 1 ; i < 8 ; )
{
buf[r] = ' ';
buf[l] = '0';
printStep(++i,buf);
buf[++l] = ' ';
buf[r--] = '1';
printStep(++i,buf);
}
return 0;
}
/////////////////////////////////
step : 1 , [ 11110000]
step : 2 , [01111000 ]
step : 3 , [0 1110001]
step : 4 , [0011100 1]
step : 5 , [00 110011]
step : 6 , [000110 11]
step : 7 , [000 10111]
step : 8 , [00001 111]
step : 9 , [0000 1111]
////////////////////////////////
[解决办法]