1

現在、1 ～ 9 の数字を繰り返しなしで使用して、9 桁のすべての数字を見つけるアルゴリズムに取り組んでいます。私は、数字をフィルタリングすることでより効率的な数独チェッカーができるという理論をテストしています。

私が実装したコードは次のことを行います。(a)(b)(c)(d)(e)(f)(g)(h)(i) = ###### のように、数字の 1 から 9 までの for ループを使用します。 ###。

私の理論では、数字の合計 (ai) が 45 に等しいかどうかをチェックすることによって、a から i までの積は 9 に等しいということです! そして、ai の逆数の合計はおよそ 2.828968 (または 1 + 1/2 + 1/3 ... 1/9) に等しい

問題は、ai の逆数の合計で 9 桁の数字をフィルター処理した後、予測される可能性のある 9 桁の数字の数が 9 未満になることです。(可能な数の実際の量)。なぜそんなにフィルタリングしているのかはわかりませんが、キャッチする数字には繰り返しがありません (これは良いことです)。

私の考えでは、ダブルスで遊んでいる方法がアルゴリズムを台無しにしているということです。

これが私のコードです：

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int product;
    int sum;
    int count=0;
    double inverseSum;
    double correctInverseSum=(1.0/1.0)+(1.0/2.0)+(1.0/3.0)+(1.0/4.0)+(1.0/5.0)+
(1.0/6.0)+(1.0/7.0)+(1.0/8.0)+(1.0/9.0);
        for(double a=1.0; a<10.0; a++){
            for(double b=1.0; b<10.0; b++){
                for(double c=1.0; c<10.0; c++){
                for(double d=1.0; d<10.0; d++){
                    for(double e=1.0; e<10.0; e++){
                        for(double f=1.0; f<10.0; f++){
                            for(double g=1.0; g<10.0; g++){
                                for(double h=1.0; h<10.0; h++){
                                    for(double i=1.0; i<10.0; i++){
                                        product=a*b*c*d*e*f*g*h*i;
                                        sum=a+b+c+d+e+f+g+h+i;
                                        if(product==9*8*7*6*5*4*3*2*1 && sum==45){
                                            inverseSum=(1.0/a)+(1.0/b)+(1.0/c)+(1.0/d)+
                                            (1.0/e)+(1.0/f)+(1.0/g)+(1.0/h)+(1.0/i);
                                            if(inverseSum==correctInverseSum)
                                            {
                                                count++;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"This is the count:"<<count<<endl;
    return 0;
}
4

5 に答える 5

2

非常に多くの for ループを見て目を洗ったので、候補は次のとおりです。

if(inverseSum==correctInverseSum)

doubles は正確に表現できるわけではないため、小さなイプシロンを使用して等しいかどうかを確認する必要があります。何かのようなもの：

if (fabs(inverseSum - correctInverseSum) < std::numeric_limits<double>::epsilon())

する必要があります#include <limits>。

于 2012-09-23T20:55:54.873 に答える
0

簡単な実験を実行してみましょう。大きいものから小さいものへの逆の合計を逆の順序で計算してみましょう。

#include <algorithm>
#include <numeric>
#include <iostream>
#include <iterator>
#include <vector>

struct generator
{
    generator(): d_value() {}
    double operator()() { return 1.0 / ++this->d_value; }
    double d_value;
};

int main()
{
    std::vector<double> values;
    std::generate_n(std::back_inserter(values), 9, generator());
    double ordered(std::accumulate(values.begin(), values.end(), 0.0));
    double reversed(std::accumulate(values.rbegin(), values.rend(), 0.0));
    std::cout << "ordered=" << ordered << " "
              << "reversed=" << reversed << " "
              << "difference=" << (reversed - ordered) << " "
              << "\n";
}

これが正確な計算である場合、明らかにこれは同じ合計をもたらすはずです。結局のところ、それらは同じ値のセットです。残念ながら、値は完全に同じではないことがわかりました。これが私に表示される出力です：

ordered=2.82897 reversed=2.82897 difference=4.44089e-16

問題は、値が正確ではなく、これらの不正確な値を2つ追加すると、エラーが発生することです。多くの場合、エラーはそれほど重要ではありませんが、結果をIDで比較しようとしても機能しません。操作の順序に応じて、異なる丸められた結果を持つ異なるオペランドが関係します。

于 2012-09-23T21:11:22.390 に答える
0

古い格言ですが、お願いです。同じことを繰り返さないでください。

乾いた状態に保ちます。

この種のコードを書いていることに気付いたときは、なぜこのように繰り返す必要があるのか​​を自問する必要があります。

他にもたくさんのオプションがあります。

1 - 再帰。コンセプトに慣れてください。

2 - i = 0 から 100 の mod 演算子 r = i % 10、c = i / 10

3 - 問題の再評価。必要以上に難しい問題を解決しようとしている

于 2012-09-23T21:13:40.053 に答える
0

チェックにはある程度のエラー許容度が必要になります。

if(fabs(inverseSum-correctInverseSum) < 1e-6) count++

または、9! を掛けると、次のようになります。

b*c*d*e*f*g*h*i + a*c*d*e*f*g*h*i ...

（各項の合計に欠落している要素が 1 つあります）。次に、浮動小数点数の代わりに整数演算を使用できます。

于 2012-09-23T20:57:43.930 に答える
0

std::bitset について聞いたことがありませんか? 検証に必要なビットは 9 ビットだけで、おそらく予算内です。

私は可変個引数テンプレートを使って練習するつもりだったので、あなたのためにこれを書きました:

#include <bitset>
#include <iostream>

template<unsigned long i>
bool test_helper(std::bitset<i> seen) {
  return seen.count() == i;
}

template<unsigned long i, typename T, typename... Args>
bool test_helper(std::bitset<i> seen, T arg1, Args... args) {
  return test_helper(seen.set(arg1 - 1), args...);
}

template<typename... Args>
bool test(Args... args) {
  return test_helper(std::bitset<sizeof... (Args)>(), args...);
}

template<unsigned long size, bool done = false>
struct Counter {
  template<typename ... Args>
  unsigned long operator()(Args... args) {
    unsigned long count = 0;
    for (int a = 1; a < 10; ++a)
      count += Counter<size, size == sizeof...(Args)+1>()(a, args...);
    return count;
  }
};

template<unsigned long i>
struct Counter<i, true> {
  template<typename ... Args>
  unsigned long operator()(Args... args) {
    return test(args...);
  }
};

int main(int argc, char** argv) {
  std::cout << Counter<9>()() << std::endl;
  return 0;
}

複雑でヒューリスティックを使用することを本当に主張する場合は、逆和を計算するための合理的な算術演算の経験を積むこともできます。明らかに、1/a iの合計は Σ j (Π i  a i )/a jであり、すべて Π i  a iで除算されます。すでに分母を計算しているので、最大値が 9 9である分子を計算するだけで済みます。しかし、それでも、ビットセットのソリューションは私にはずっと簡単に思えます。

于 2012-09-24T06:13:33.760 に答える