0

これは、数独 (9x9) を解くためのコードです。

#include <iostream>
#define dim 9
#define br_polja dim*dim

using namespace std;


bool Fsearch (int tab[dim][dim],int *x,int *y, int cand[dim], int *num_cand, int &free) {
int min=9; 
*x=-1;
*y=-1;
free=0;
for (int i=0;i<dim;i++) {
    for (int j=0;j<dim;j++) {

        if (tab[i][j]!=0) continue;
        free+=1;
        *num_cand=0;
        int cand_f[dim];
        for (int w=0;w<dim;w++)
            cand_f[w]=1;  

        int p,q; 
        p=i+3-(i%3); 
        q=j+3-(j%3);

        for (int w=p-3;w<p;w++) 
            for (int r=q-3;r<q;r++)
                if (tab[w][r]!=0){        
                                   cand_f[tab[w][r]-1]=0;
                                   }

        for (int w=0;w<dim;w++) { 
            if (tab[w][j]!=0) cand_f[tab[w][j]-1]=0; 
            if (tab[i][w]!=0) cand_f[tab[i][w]-1]=0;
            }

        for (int w=0;w<dim;w++)
            if (cand_f[w]!=0) 
               *num_cand+=1;


        if (*num_cand==1) { 
                                   *x=i;
                                   *y=j;
                                   int z=0;
                                   for (int w=0;w<dim;w++)
                                       if (cand_f[w]!=0) { 
                                          cand[z]=w+1;
                                          z++;
                                          }
                                   return true;
                                   }
        else if (*num_cand<min && *num_cand>0) {
                                     int z=0;
                                     for (int w=0;w<dim;w++)
                                         if (cand_f[w]!=0) { 
                                            cand[z]=w+1;
                                            z++;
                                            }
                                     min=*num_cand;
                                     *x=i;
                                     *y=j;
                                     }
        else if (*num_cand==0) {
             return false;
             }
        } 
    } 

    *num_cand=min;
    if (free<1) return false;
    else return true;           
}

bool Fsudoku(int tab[dim][dim]) {
 int free=0;

 int x,y;
 int cand[dim];
 int num_cand;
 brojacK=0;
 if (!Fsearch(tab,&x,&y,cand, &num_cand,free)) {
                                               if (free==0) return true;
                                               else return false;
                                               }


 for (int i=0;i<num_cand;i++) {
     tab[x][y]=cand[i];
     if (Fsudoku(tab)) return true;
     else tab[x][y]=0;
     }
 return false;

 }

このアルゴリズムを Big O または Big Theta 表記で分類するのを手伝ってくれる人がいますか? 私は O(n^3) を取得しましたが、ご覧のとおり、そうではありません! それで、どうやって始めるかのヒントやアドバイスをください。とても感謝しています。必要に応じて、これを疑似コードで投稿することもできます。

ありがとう、MB

4

1 に答える 1

0

Big O は、どの用語が支配的かについてです。

では、各ループは何回実行されるのでしょうか?

それらは固定長ですか、それとも変化しますか?

実行時間に影響を与える可能性のある変更可能なパラメーターは何ですか?

于 2013-07-10T23:10:30.433 に答える