0

素数2、3、5を使用してシーケンスを生成し、シーケンスのn番目の数値を表示するという問題に取り組んでいます。したがって、プログラムに1000番目の数値を表示するように要求すると、それが表示されるはずです。

基本的な決定とループだけで、配列などを使用することはできません。

私はそれに取り組み始めて壁にぶつかりました...これが私が得たものです：

#include <iostream>

using namespace std;
int main() {
    unsigned int n=23;
    for(int i=2; i<n; i++){
        if(i%2==0){
            cout<<i<<", ";
        }else if(i%3==0){
            cout<<i<<", ";
        }else if(i%5==0){
            cout<<i<<", ";
        }
    }

    return 0;
}

残念ながら、そのコードは必要なことを実行しません。素数7を含む14などの数値が表示されます。数値は、指定された3つの素数（2、3、5）でのみ除算できます。

私が理解しようとしているいくつかの情報を見つけましたが、それを実装する方法が今のところわかりません...多分たくさんのfor（）ループを使用していますか？したがって、2 ^ n * 3 ^ m * 5 ^ kの概念を使用する必要があるようです。ここで、n + m +k>0です。

最初に2^1 * 3 ^ 0 * 5 ^ 0で完全に割り切れるかどうかを確認し、次に2 ^ 0 * 3 ^ 1 * 5 ^ 0、次に2 ^であるかどうかを確認するテストで、数値を実行する必要があると思います。 0 * 3 ^ 0 * 5^1など...どこから始めればよいかわからない。

4

4 に答える 4

3

これは、リチャード・ハミングにちなんでハミングの問題と呼ばれる有名な問題であり、ダイクストラによる有名な著書「プログラミングの規律」で取り上げられています。数学者はこれらの数を（1を含めると）5と呼びます。素数分解には5以下の素数しか含まれていないため、5の滑らかな数です。

あなたが気付くはずのことは、あなたがお互いから数を生成することができるということです。問題について考える1つの方法は次のとおりです。

#include <set>
#include <iostream>

using namespace std;

int
main()
{
    const unsigned n = 23;

    set<unsigned> s;
    s.insert(2);
    s.insert(3);
    s.insert(5);

    for (unsigned i = 0; i < n; ++i)
    {
        // This returns the smallest element in the set.
        unsigned x = *s.begin();
        cout << x << '\n';

        // Erase the smallest element.
        s.erase(s.begin());

        // Insert the multiples of x.
        s.insert(2*x);
        s.insert(3*x);
        s.insert(5*x);
    }
}

これには、n個の数値を出力するのにO（n log n）時間がかかります。レイジーストリームをマージすることにより、同様のアルゴリズムを使用してO（n）時間でそれを行うことが可能です。私のソリューションはとを使用boost::transform_iteratorしboost::iterator_facadeたので、初心者にはお勧めしません。

于 2013-01-24T04:02:20.747 に答える
0

このコードはそれを行います。問題をより小さな問題に分割することは、多くの場合、良い計画です。

int main() {
    unsigned int n=23;

    unsigned int counter=0;
    unsigned int answer;
    for ( answer = 2; counter < n; ++answer ) {
        if ( isNotDivisibleByAPrimeGreaterThan5( i ) {
           ++counter;
        }
    }
    cout << answer;
    return 0;
}

これで、この関数を作成するだけで済みます。

bool isNotDivisibleByAPrimeGreaterThan5( unsigned int i ) {
  // return true if i is not divisable by a prime greater than 5.
}
于 2013-01-24T03:47:59.593 に答える
0 
#include <type_traits>
#include <utility>
#include <iostream>

template<int... s>
struct seq {};

template<int n, typename seq, typename=void>
struct can_be_factored_into;

template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && (n%first) >::type >: can_be_factored_into< n, seq<rest...> > {};

template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && !(n%first) >::type >: can_be_factored_into< n/first, seq<first, rest...> > {};

template<int n, int... rest>
struct can_be_factored_into< n, seq<rest...>, typename std::enable_if< n == 1 >::type: std::true_type {};

template<int n>
struct can_be_factored_into< n, seq<>, typename std::enable_if< n != 1 >::type: std::false_type {};

template<int n>
using my_test = can_be_factored_into< n, seq<2,3,5> >;

template<template<int n>class test, int cnt, int start=1, typename=void>
struct nth_element;

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt>1)&&test<start>::value >::type >:
  nth_element<test, cnt-1, start+1 > {};

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt==1)&&test<start>::value >::type >
  { enum { value = start }; };

template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< !test<start>::value >::type >:
  nth_element<test, cnt, start+1 > {};

int main() {
  std::cout << nth_element< my_test, 1500 >::value << "\n";
}

上記のコードをコンパイルすると、1分もかからずに実行されます。

欠点は、ほとんどのコンパイラのコンパイル時の再帰制限を超えることです。（これはあなたの毎日の控えめな表現でした）

これを改善するnth_elementには、指数関数的な爆発検索と分割統治をその範囲内で実行するように書き直す必要があります。上記のシーケンスの1500番目の要素は2^32より大きい可能性があるため、64ビット値で動作するようにコードを変更する必要がある場合もあります。

それとも、高速でコンパイルする必要がありますか？:)

そして、これがハミング実装の最初のパスです。まだコンパイルされていません：

#include <iostream>
#include <utility>

template<long long... s>
struct seq;

template<long long cnt, typename seq, typename=void>
struct Hamming;

template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt == 0 >::type> {
  static const long long value = first;
};

template<long long x, typename seq>
struct prepend;
template<long long x, long long... s>
struct prepend<x, seq<s...>>
{
  typedef seq<x, s...> type;
};

template<typename s1, typename s2, typename=void>
struct merge;

template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 < begin_s2) >::type > {
  typedef typename prepend< begin_s1, typename merge< seq< s1... >, seq< begin_s2, s2... > >::type >::type type;
};

template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 >= begin_s2) >::type > {
  typedef typename prepend< begin_s2, typename merge< seq< begin_s1, s1... >, seq<  s2... > >::type >::type type;
};
template<long long begin_s1, long long... s1>
struct merge< seq< begin_s1, s1... >, seq<>, void > {
  typedef seq< begin_s1, s1... > type;
};
template<long long... s2>
struct merge< seq<>, seq<s2...>, void > {
  typedef seq< s2... > type;
};

template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt != 0 >::type>:
  Hamming<cnt-1, typename merge< seq<first*2, first*3, first*5>, seq<rest...> >::type >
{};

int main() {
  std::cout << Hamming<1500, seq<1>>::value << "\n";
};
于 2013-01-24T04:06:55.423 に答える
-1

これをチェックして。 

#include <iostream>
using namespace std;

int IsPrime(int var);
int CheckifPrimeGreaterThaFive(int Num);
int GetFactors(int Num)
{
    int i =0,j=0;
    for (i =2,j=0; i <= Num; i++)
    {
        if (Num%i == 0)
        {
           if (1 == CheckifPrimeGreaterThaFive(i))
           {
                 return 1;
              }
        }
    }
    return 0;
}

int CheckifPrimeGreaterThaFive(int Num)
{
   if ((Num != 2 && Num != 3 && Num != 5) && IsPrime(Num))
   {

           return 1;
   }

    return 0;
}

int IsPrime(int var)
{
    for (int i = 2; i <= var/2; i++)
    {
        if (var % i == 0)
           return 0;
    }
    return 1;
}


int main() {
    int n=98;
    int i, FactorsCount=0;

    for(i=2; i<n; i++)
    {
        if (0 == GetFactors(i))
        {  
           cout<<" "<<i;
        }   
    }
    return 0;
}
于 2013-01-24T05:58:07.357 に答える