0

在打印出找到的第一个解决方案后，我想打印找到第一个解决方案所花费的时间，如下所示。

输入 N：4

1 3 0 2

时间：0.001秒

但是，当我输入 30 作为输入时，它需要异常长的时间，就好像它处于无限循环中一样。此外，当我输入 31 作为输入时，我花了将近 15 秒，但打印出来的时间只有 0.002 秒。我认为我应该更改时钟功能的位置，但由于代码在打印出第一个解决方案后退出程序，因此我决定将它们放在哪里变得非常棘手。

任何帮助将不胜感激。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int put_queens(int column, int size, int* array);
int check_safe(int column, int row, int* array);
void print_sol(int size, int* array);

int main (void){
    int size, flag;
    int* array;
    clock_t t;
    printf("Input N: ");
    scanf("%d",&size);

    array = (int*) calloc(size, sizeof(int));

    t = clock();
    flag = put_queens(0,size, array);
    if(flag){
        printf("No solution");
        t = clock() - t;
        printf("\nTime: %.3fsec",((float)t)/CLOCKS_PER_SEC);
        free(array);
    }

    return 0;
}

int put_queens(int column, int size, int* array){
    clock_t t;
    t = clock();
    int row, flag;
    for( row = 0; row < size; row++ ){
        if( check_safe(column, row, array) ){
            array[column] = row;
            if(column == size - 1){
                print_sol(size, array);
                t = clock()-t;
                printf("\nTime: %.3fsec",((float)t)/CLOCKS_PER_SEC);
                free(array);
                exit (0);
            }
            else{
                put_queens(column + 1, size, array);
            }
        }
    }
    if(row == size && column == size - 1){
        flag = 1;
    }
    return flag;
}

int check_safe(int column, int row, int* array){
    int index;
    for(index = 0; index < column; index++){
        if((array[index] == row ) || (abs(array[index]-row)==abs(column - index))){
            return 0;
        }
    }
    return 1;
}

void print_sol(int size, int* array){
    int column;
    for(column = 0; column < size; column++ ){
        printf("%3d", array[column]);
    }
}
4

1 回答 1

0

请参阅以下两个条件和您的 for 循环：

for( row = 0; row < size; row++ ){
    if( check_safe(column, row, array) ){
        array[column] = row;
        if(column == size - 1){
            print_sol(size, array);
            t = clock()-t;
            printf("\nTime: %.3fsec",((float)t)/CLOCKS_PER_SEC);
            free(array);
            exit (0);
        }
        else{
            put_queens(column + 1, size, array);
        }
    }
}

在上面的第一个 if 条件满足时，它将检查第二个条件 if (column == size -1)。如果满足第一个条件但“列”值已经大于“大小”，则永远不会满足第二个条件（例如列 = 31 和大小 = 30），递归将永远持续下去，这是需要很长时间的原因之一在某些情况下时间。将第二个 if 条件更正为 if(column > size)。同样从 for 循环中，您正在递归地调用函数，因此满足第二个 if 条件和递归几乎无法控制也变得更加关键，因为对于每个递归，它都有一个 for 循环，而 for 循环再次递归地调用该方法。想象一下这里发生了什么。由于存在递归调用的限制，操作系统会突然终止您没有看到任何程序输出的进程。关于您的时钟，请用一些打印声明检查它是否正确获取时间。更改逻辑，使递归不应该永远持续下去。顺便问一下，你想在这里实现什么？

于 2017-10-09T15:20:32.460 回答