POJ 2718 Smalles Difference(尽きるまで捜索)

6728 ワード

暴力

http://poj.org/problem?id=2718
一つの数を一つの刀に切って二つの数に分解して、二つの数は一つの数字の順番に変えられますが、先頭0があるわけではありません.この二つの数の差の最小値を求めます.
検索を使用して再帰性を回避し,より良いアルゴリズムとして自認した.
最初に思いつきましたが、列挙してすぐに実現しました.

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include 
#include 
#include 
using namespace std;
 
///SubMain//
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string all;
        getline(cin, all);
        all.erase(remove(all.begin(), all.end(), ' '), all.end());
        int result = 0x3F3F3F3F;
        int cut = all.size() / 2;
        do 
        {
            string s1 = all.substr(0, cut);
            string s2 = all.substr(cut);
            if ((s1[0] == '0' && s1.size() > 1) ||
                (s2[0] == '0' && s2.size() > 1)
                )
            {
                continue;
            }
            int n1 = atoi(s1.c_str());
            int n2 = atoi(s2.c_str());
            int dif = abs(n1 - n2);
            if (dif < result)
            {
                result = dif;
            }
        } while (next_permutation(all.begin(), all.end()));
         
        cout << result << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///End Sub//

TLEを予想していませんでしたが、ここの複雑さはO(length!)nで、length=10の時には、内部層は3628800回の循環に達しています.用例は多いかもしれません.
工夫を凝らして最適化するには、まずシミュレーションの方法に変えて、パリティに分けて検討したいと思いますが、このテーマは2.1の最も基礎的な「尽きる捜索」でこのセクションを徹底的に捜索することです.目的は検索アルゴリズムを訓練することです.
そこで引き続き捜索するルートを歩いて、上のプログラムはなぜ遅くて、繰り返し計算するためです.例えば、最初の文字列が12で、第二の文字列が34である場合と、最初の文字列が34であり、第二の文字列が12である場合とは異なる場合とみなされる.これは最適化すべき最初のポイントです.
第二のポイントはstringタイプの全席操作がかかります.ビット演算で最適化できます.
一部の人がdfsで再帰するのを見ましたが、違和感があります.コードがよく分かりません.
私は一番好きなおもちゃを使いました.

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include 
#include 
#include 
#include 
using namespace std;
 
///SubMain//
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n;
    cin >> n;
    cin.ignore();
    while (n--)
    {
        string all;
        getline(cin, all);
        all.erase(remove(all.begin(), all.end(), ' '), all.end());
        int length = all.size();
        int cut = length / 2;
        int permute = 1 << length;
        int result = 0x3F3F3F3F;
        do
        {
            bitset<10> used = static_cast>(permute);
            string s1, s2;
            for (int i = 0; i < length; ++i)
            {
                if (used[i])
                {
                    s1 += all[i];
                }
                else
                {
                    s2 += all[i];
                }
            }
            if (s1.size() != cut)
            {
                continue;
            }
            if (s1[0] == '0' && s1.size() > 1)
            {
                continue;
            }
            // s1 s2         
            //     
            do
            {
                int n1 = atoi(s1.c_str());
                do
                {
                    if (s2[0] == '0' && s2.size() > 1)
                    {
                        continue;
                    }
                    int n2 = atoi(s2.c_str());
                    int dif = abs(n1 - n2);
                    //cout << s1 << ' ' << s2 << " dif " << dif << " result: " << result << endl;
                    if (dif < result)
                    {
                        result = dif;
                    }
                } while (next_permutation(s2.begin(), s2.end()));
            } while (next_permutation(s1.begin(), s1.end()));
        } while (--permute);
 
        cout << result << endl;
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("out.txt");
#endif
    return 0;
}
///End Sub//

違います.いや、分かりにくいですよね.このコードのために、多くのことを勉強しましたが、やはり面倒くさいと思います.それでコードを追加しました.

#include
#include
#include
#include
#define INF 0x3f3f3f3f
using namespace std;

int a[15];
int n;

void solve()
{
    while(a[0]==0)
        next_permutation(a,a+n);

    int ans=INF;
    int mid=(n+1)/2;
    do
    {
        if(a[mid])
        {
            int x=a[0],y=a[mid];
            for(int i=1;iabs(x-y))
                ans=abs(x-y);
        }

    }while(next_permutation(a,a+n));
    cout<

ハハ、まだ吐いてないならdfsコードをもう一つお願いします.

#include 
#include 
#include 
#include 
using namespace std;

const int MAX_N = 11;
int ans, n;
int a[MAX_N], b[MAX_N];
bool used[MAX_N];

void solve(int aa) {
    int m = 0;
    for (int i = 0; i < n; ++ i) {
        if (!used[i]) {
            b[m++] = a[i];
        }
    }

    do {
        int bb = 0;
        for (int i = 0; i < m; ++ i) {
            bb = bb*10 + b[i];
        }

        if (b[0] != 0 || m == 1) {
            ans = min(ans, abs(aa - bb));
        }
    }while(next_permutation(b, b + m));
}

void dfs(int k, int r) {
    if (k == n/2) {
        solve(r);
    } else {
        for (int i = 0; i < n; ++ i) {
            if (!used[i]) {
                if (a[i] == 0 && k == 0 && n > 3) continue;
                used[i] = true;
                dfs(k+1, r*10+a[i]);
                used[i] = false;
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int t;
    scanf("%d
", &t);
    char str[25];

    while(t --) {
        gets(str);
        n = 0;
        for (int i = 0; str[i] != '\0'; ++ i) {
            if(str[i] >= '0' && str[i] <= '9') {
                a[n++] = str[i] - '0';
            }
        }
        memset(used, false, sizeof(used));
        ans = INT_MAX;
        dfs(0, 0);
        printf("%d
", ans);
    }
    return 0;
}

JavaScriptにおける計算精度が失われた問題(一)