https://stackoverflow.com/questions/502443
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
現在、プログラミング スキルを練習するためにいくつかの質問に挑戦しています。（まだ学校などで受けていません。独学です）指定されたtxtファイルから数字を読み取る必要があるこの問題に遭遇しました。この数字は N になります。ここで、N <= 10 000 の N 番目の素数を見つけるとします。それを見つけたら、別の txt ファイルに出力すると思います。これで、質問の大部分については理解でき、N を取得する方法を考案することができました。問題は、配列を使用して以前に見つかった素数を保存し、将来の数値と照合するために使用していることです。配列のサイズが 100 の場合でも、入力整数がおよそ 15 未満である限り、プログラムはクラッシュします。
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main() {
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime;
trial >> prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[100], b, c, e;
bool check;
b = 0;
switch (prime) {
case 1:
{
write << 2 << endl;
break;
}
case 2:
{
write << 3 << endl;
break;
}
case 3:
{
write << 5 << endl;
break;
}
case 4:
{
write << 7 << endl;
break;
}
default:
{
for (int a = 10; a <= 1000000; a++) {
check = false;
if (((a % 2) != 0) && ((a % 3) != 0) && ((a % 5) != 0) && ((a % 7) != 0)) // first filter
{
for (int d = 0; d <= b; d++) {
c = num[d];
if ((a % c) == 0) {
check = true; // second filter based on previous recorded primes in array
break;
}
}
if (!check) {
e = a;
if (b <= 100) {
num[b] = a;
}
b = b + 1;
}
}
if ((b) == (prime - 4)) {
write << e << endl;
break;
}
}
}
}
trial.close();
write.close();
return 0;
}
私はこれを完全にダミーガイドと私自身に基づいて実行したため、コードの非効率性とアルゴリズムの全体的な初心者っぽさはご容赦ください。また、15 までは素数が正しく表示されます。
この現在のコードをどのように改善すればよいか誰か教えていただけませんか?配列の代わりにtxtファイルを使用することを考えています。それは可能ですか？助けていただければ幸いです。
解決 13
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <fstream>
using namespace std;
int main()
{
ifstream trial;
trial.open("C:\\Users\\User\\Documents\\trial.txt");
int prime, e;
trial>>prime;
ofstream write;
write.open("C:\\Users\\User\\Documents\\answer.txt");
int num[10000], currentPrime, c, primePrint;
bool check;
currentPrime=0;
num[currentPrime] = 2;
currentPrime=1;
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false;
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++)
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;}
}
if (!check)
{ e=currentInt;
if( currentInt!= 2 ) {
num[currentPrime]= currentInt;}
currentPrime = currentPrime+1;}
if(currentPrime==prime)
{
write<<e<<endl;
break;}
}
trial.close();
write.close();
return 0;
}
これは私の元のコードの最終版ベースです。それは完璧に動作し、あなたが素数の範囲を増やしたい場合は、単に配列の数を増やします。助けてくれてありがとう=）
他のヒント
あなたの質問は数学ではなくプログラミングに関するものなので、私もそのように答えようと思います。
コードを一目見ると、一体ここで何をしているのかと不思議に思います...回答を読むと、コードをわざわざ理解しようとしない人もいれば、コードをデバッガにダンプして何が起こっているかを確認するだけの人もいることがわかります。私たちはそんなにせっかちなのでしょうか？それとも、比較的簡単な問題に対してコードが難しすぎて理解できないだけでしょうか?
コードを改善するには、いくつかの質問を自問してみてください。
- とは何ですか
a,b,c, 、など？もっと分かりやすい名前を付けた方が良いのではないでしょうか？ - あなたのアルゴリズムは正確には何ですか?あなたは自分がやっていることについて（正確な方法で）英語で明確に書かれた段落を書き留めることができますか?その段落を、あらゆる入力に対して頭の中で実行でき、それが正しいことを確信できる一連のステップに変更できますか?
- すべての手順が必要ですか?それらのいくつかを組み合わせたり、削除したりすることはできますか?
- 英語で表現するのは簡単だが、C/C++ ではたとえば 10 行以上必要となるステップは何ですか?
- ステップのリストには何らかの構造がありますか?ループ？サブステップを含む 1 つのステップとして配置できる大きな (おそらく繰り返される) チャンクですか?
質問に答えた後は、おそらく、問題を解決する、説明しやすく理解しやすい、明確にレイアウトされた疑似コードが作成されるでしょう。その後、疑似コードを C/C++、または実際には任意の汎用言語で実装できます。
素数性をテストするには、次の 2 つの方法を検討してください。
- 問題の領域は十分に小さいため、N 番目の素数が見つかるまで数値をループするだけでおそらく許容可能な解決策となり、完了までに数ミリ秒もかかりません。このアプローチには簡単な最適化が多数あります。たとえば、2 で割り切れるかどうかをテストする必要があるのは 1 回だけで、その後は奇数と照合するだけで済み、次の数をチェックするだけで済みます。テストされる数値の平方根になります。
- エラトステネスのふるい 非常に効果的で実装が簡単で、数学的な処理が信じられないほど軽量です。
コードがクラッシュする理由については、次の行を変更したのではないかと思われます
for( int d=0; d<=b; d++)
に
for( int d=0; d<b; d++)
おそらくガベージが含まれている、初期化されていない可能性のある配列要素から読み取ろうとしているため、問題は解決します。
私はあなたのコードを見ていないが、あなたの配列は、あなたがそれに保存するすべての値を格納するのに十分な大きさでなければなりません。 100は確かに、この問題の最も入力のために十分であることを行っていません。
例えば。このコード..
int someArray[100];
someArray[150] = 10;
は、アレイ（150> 100）よりも大きい場所に書き込みます。これは、メモリの上書きとして知られています。あなたのプログラムはすぐに、後で、または決してすべてでクラッシュすることがあり、そのメモリ位置にあると何が起こったかに応じています。
良い練習配列を使用したときにあなたが書いている要素が配列の境界内にあることを何らかの方法で主張することです。あるいは、このチェックを実行するアレイ型クラスを使用します。
あなたの問題のために最も簡単な方法は、STLベクトルクラスを使用することです。あなたは要素を（ベクトル::一back（））を追加する必要がありますが、あなたは、配列演算子[]を使用して、後でアクセス要素をすることができます。ベクターはまた、あなたに最高の反復の性能が得られます。
ここでは、ベクターに番号0-100を追加し、それらを印刷するいくつかのサンプルコードです。私たちは、ベクターに格納されているアイテムの数を使用して第二のループに注意します。
#include <vector> // std::vector
...
const int MAX_ITEMS = 100;
std::vector<int> intVector;
intVector.reserve(MAX_ITEMS); // allocates all memory up-front
// add items
for (int i = 0; i < MAX_ITEMS; i++)
{
intVector.push_back(i); // this is how you add a value to a vector;
}
// print them
for (int i = 0; i < intVector.size(); i++)
{
int elem = intVector[i]; // this access the item at index 'i'
printf("element %d is %d\n", i, elem);
}
私はちょうどすぐにふるいをコード化されたので、現時点では私の関数型プログラミングを改善しようとしています。私はそれをここに投稿します把握します。あなたはまだ学習している場合は、あまりにも、それは面白いかもしれません。
#include <iostream>
#include <list>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;
class is_multiple : public binary_function<int, int, bool>
{
public:
bool operator()(int value, int test) const
{
if(value == test) // do not remove the first value
return false;
else
return (value % test) == 0;
}
};
int main()
{
list<int> numbersToTest;
int input = 500;
// add all numbers to list
for(int x = 1; x < input; x++)
numbersToTest.push_back(x);
// starting at 2 go through the list and remove all multiples until you reach the squareroot
// of the last element in the list
for(list<int>::iterator itr = ++numbersToTest.begin(); *itr < sqrt((float) input); itr++)
{
int tmp = *itr;
numbersToTest.remove_if(bind2nd(is_multiple(), *itr));
itr = find(numbersToTest.begin(), numbersToTest.end(), tmp); //remove_if invalidates iterator
// so find it again. kind of ugly
}
// output primes
for(list<int>::iterator itr = numbersToTest.begin(); itr != --numbersToTest.end(); itr++)
cout << *itr << "\t";
system("PAUSE");
return 0;
}
これを改善する方法について何かアドバイスは道によって歓迎されるでしょう。
ここに私のコードです。大きな数で作業する場合、それは非常に遅いです！ これは、数にして、あなたの入力をすべての素数を計算することができます！
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int m;
int n=0;
char ch;
fstream fp;
cout<<"What prime numbers do you want get within? ";
if((cin>>m)==0)
{
cout<<"Bad input! Please try again!\n";
return 1;
}
if(m<2)
{
cout<<"There are no prime numbers within "<<m<<endl;
return 0;
}
else if(m==2)
{
fp.open("prime.txt",ios::in|ios::out|ios::trunc);//create a file can be writen and read. If the file exist, it will be overwriten.
fp<<"There are only 1 prime number within 2.\n";
fp<<"2\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
else
{
int j;
int sq;
fp.open("prime.txt",ios::in|ios::out|ios::trunc);
fp<<"2\t\t";
n++;
for(int i=3;i<=m;i+=2)
{
sq=static_cast<int>(sqrt(i))+1;
fp.seekg(0,ios::beg);
fp>>j;
for(;j<sq;)
{
if(i%j==0)
{
break;
}
else
{
if((fp>>j)==NULL)
{
j=3;
}
}
}
if(j>=sq)
{
fp.seekg(0,ios::end);
fp<<i<<"\t\t";
n++;
if(n%4==0)
fp<<'\n';
}
}
fp.seekg(0,ios::end);
fp<<"\nThere are "<<n<<" prime number within "<<m<<".\n";
fp.close();
cout<<"Congratulations! It has worked out!\n";
return 0;
}
}
が1の場合、あなたは以下のコードがあるだろう（常に良いことです！）あなたは3、5と7のための特殊なケースを持っていなかった場合。
また、あなたは2のための特別なケースを避けることができれば、あなただけの設定NUM [B] = 2としているアレイで物事によって割り切れるための唯一のテストます。
これは次のようになります。
あなたは、配列の末尾からメモリにアクセスするため、すると、これはクラッシュになります：
for (int d = 0; d <= b; d++) {
c = num[d];
私はあなたの頭の中でアルゴリズムが明確に取得し、再度コードをアプローチする必要があると思います。
デバッガを通して、あなたのコードを実行すると、私はそれが「if ((a % c) == 0)」の浮動小数点例外でクラッシュすることを発見しました。この理由は、あなたがNUMには何も初期化されていないということですので、あなたは「％0」をやってます。
あなたはそれで100万にフィットすることはできませんので、私が知っていることから、Cに/ C ++ intが16ビットのタイプは（制限が2 ^ 16 = 32Kである）です。試してみて、宣言「」限り、
私はC標準がintは、少なくともshortほどの大規模で最もlongほどの大きさであることを述べていると考えています。
練習intで4バイトであるので、-2^31と2^31-1間番号を保持することができる。
、私はエラトステネスするのふるいを実装することをお勧め。
これはまた、あなたが興味を持つようになります。 http://en.wikipedia.org/wiki/ Primality_testする
for(int currentInt=2; currentInt<=1000000; currentInt++)
{check = false; // Basically the idea for this for loop is to run checks against integers. This is the main for loop in this program. I re initialize check to false ( check is a bool declared above this. )
for( int arrayPrime=0; arrayPrime<currentPrime; arrayPrime++) // This for loop is used for checking the currentInt against previously found primes which are stored in the num array.
{ c=num[arrayPrime];
if ((currentInt%c)==0) { check = true;// second filter based on previous recorded primes in array
break;} // this is the check. I check the number against every stored value in the num array. If it's divisible by any of them, then bool check is set to true.
if ( currentInt == 2)
{ check = false; } // since i preset num[0] = 2 i make an exception for the number 2.
if (!check)
{
e=a;
if(currentPrime <= 100){
num[currentPrime]= currentInt;} // This if uses check to see if the currentInt is a prime.
currentPrime = currentPrime+1;} // increases the value of currentPrime ( previously b ) by one if !check.
if(currentPrime==prime)
{
write<<e<<endl;
break;} // if currentPrime == prime then write the currentInt into a txt file and break loop, ending the program.
アドバイスpolythinkerをありがとう=）
