C語言問題 暴風雨大海中好水手登上救生艇

/* Not the best and there are rooms to optimize and should have more
error checking. Developed on Linux with gcc. */

#include

typedef struct C {
char ch;
struct C * next;
struct C * prev;
} cell;

cell *head=NULL;
char input[ 256 ];

void enqueue( char c )
{
cell *ptr = (cell *) malloc( sizeof( cell ));
cell *tmp;

ptr->ch = c;
if ( head == NULL ) {
head = ptr;
ptr->next = ptr;
ptr->prev = ptr;
} else {
tmp = head;
while ( tmp->next != head ) {
tmp = tmp->next;
}
tmp->next = ptr;
ptr->prev = tmp;
ptr->next = head;
head->prev = ptr;
}
}

int dequeue( int i )
{
cell * tmp=head;

if ( tmp == NULL ) {
return 0;
}
while ( --i != 0 ) {
tmp = tmp->next;
}
if ( tmp->ch == 'X' ) {
return 0;
}
if (( tmp == head ) && ( tmp->next == head )) {
head = NULL;
} else {
head = tmp->next;
tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
}
(void) free( tmp );
return 1;
}

int is_done()
{
cell *tmp=head;

if ( tmp == NULL ) {
return 1;
} else if ( tmp->ch != 'X' ) {
return 0;
} else {
tmp = tmp->next;
while (( tmp->ch == 'X' ) && ( tmp != head )) {
tmp = tmp->next;
}
if ( tmp != head ) {
return 0;
} else {
return 1;
}
}
}

int check( int i )
{
while ( !is_done() && dequeue(i)) {
}
if ( is_done()) {
return 1;
} else {
return 0;
}
}

void reset()
{
int i;
cell *tmp, *ptr;

head->prev->next = NULL;
tmp = head->next;
while ( tmp != NULL ) {
ptr = tmp->next;
(void) free( tmp );
tmp = ptr;
}
head = NULL;
for ( i=0; i < strlen( input ); i++ ) {
enqueue( input[ i ]);
}
}

main()
{
int i;

printf("prompt: ");
scanf( "%s", input );

for ( i=0; i < strlen( input ); i++ ) {
enqueue( input[ i ]);
}

i = 1;
while ( !check(i) ) {
reset();
i++;
}
printf("%d\n", i);
}

2010-11-25 13:14:40 補充：
The first line should be:
#include

The output should look like:
prompt: OOXXOXXX
10

2010-11-25 13:29:39 補充：
#&#060;include&#062;

2010-11-25 13:31:07 補充：
I am giving up on this feature of removing special characters. Your account does not allow me to send you the source code so I can't send that to you. However, you should notice that the include line is missing stdio.h.

2010-11-25 13:53:53 補充：
If you are using windows, you will need to put a system("pause") statement towards the end of the main() function.

這問題可以用遞迴解：

#include<stdio.h>
#include<stdlib.h>
#include <string.h>

/**
尋找num是否存在arr陣列中的函數
*/
int contains(int arr[],int arrayLen, int num){
if(arrayLen < 1)
return 0;
while(--arrayLen >= 0){
if(arr[arrayLen] == num)
return 1;
}
return 0;
}

int retrieveGoodSailer( int memberCount,int startIndex, int magicNumber,
int marks[], int badSailerCount){

/** 計算以magicNumber，會數到哪個水手(陣列從0開始，因此magicNumber-1) */
int nextIndex = (startIndex+magicNumber-1) % memberCount;
int i;

if(memberCount == badSailerCount) //結束條件為剩下的水手都是壞水手
return 1;

if( !contains(marks, badSailerCount, nextIndex)){ //若數到的不是壞水手

/* 將數到的水手位置後方的壞水手全部挪前一個位置 */
for( i = 0 ; i < badSailerCount; i++ ){
if(marks[i] >= nextIndex)
marks[i]-=1;
}
/** 將水手數-1，以目前數到的位置為啟始點，繼續遞迴呼叫，直到滿足結束條件*/
if( retrieveGoodSailer(memberCount-1, nextIndex ,
magicNumber, marks, badSailerCount)){
return 1;
}
/** 否則，則將往前挪的水手位置往後挪(也就是還原呼叫前的狀態) */
else{
for( i = 0 ; i < badSailerCount; i++ ){
if( marks[i] >= nextIndex)
marks[i]+=1;
}
return 0;
}
}
//數到的是壞水手，直接return 0。
return 0;
}

int main(){
char str[20]; //記錄使用者輸入的陣列
int marks[20]; //紀錄壞水手位置的陣列
printf("請輸入好水手與壞水手的組合( O為好水手,X為壞水手): \n");
scanf("%s",str);
int badSailerCount = 0;
int memberCount = strlen(str);
int magicNumber = 1;

// 將壞水手位置資訊存入marks陣列
int i;
for( i = 0; i < memberCount; i++){
if(str[i] == 'X')
marks[badSailerCount++] = i;
}

/** magicNumber從1開始，每次遞增，直到找到答案為止 */
while(badSailerCount != 0 &&
retrieveGoodSailer(memberCount, 0, magicNumber, marks, badSailerCount) == 0){
magicNumber++;
}

if(memberCount == badSailerCount) //全都是壞水手則無解
printf("No answer");
else
printf("Answer: %d", magicNumber);

system("pause");
return 0;
}