1

我目前正在研究一种算法，以使用数字 1-9 查找所有 9 位数字而没有任何重复。我正在测试一个理论，我认为这样的过滤数字将使数独检查器更有效。

我实现的代码执行以下操作。它对数字中的 1-9 位置使用 for 循环，例如 (a)(b)(c)(d)(e)(f)(g)(h)(i) = ###### ###。

我的理论是，通过检查数字 (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 不能完全表示，因此您必须使用一个小的 epsilon 检查是否相等。就像是：

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

你需要#include <limits>。

于 2012-09-23T20:55:54.873 回答
0

你没听说过 std::bitset 吗？您只需要 9 位即可验证，这可能在您的预算之内。

我一直想对可变参数模板进行一些练习，所以我为你写了这个：（c ++ 11专家，随意将它撕成碎片。）

#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。但是，bitset 解决方案对我来说似乎要简单得多。

于 2012-09-24T06:13:33.760 回答
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 ...

（每一项总和中缺少一个因素）。然后你可以使用整数算术而不是浮点数。

于 2012-09-23T20:57:43.930 回答
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

问题是这些值不准确，并且添加其中两个不准确的值会引入一些错误。通常错误并不重要，但尝试比较结果的身份将不起作用：根据操作的顺序，涉及具有不同舍入结果的不同操作数。

于 2012-09-23T21:11:22.390 回答