A 回答 (9件)
- 最新から表示
- 回答順に表示
No.8
- 回答日時:
そうか, 考えてみれば
#include <stdio.h>
#include <stdlib.h>
int main()
{
int val = 1;
int factors, i;
for (factors = 0; (val *= 2) <= 10000; ++factors) {
;
}
printf("%d = 2", val);
for (i = 1; i < factors; ++i) {
printf(" * 2");
}
printf("\n因子数: %d\n", factors);
return EXIT_SUCCESS;
}
でいいのか.
本題とは全く関係ないのですが, 出力部分があやしい気がします>#7.
符号なしなら d じゃなくて u だろとか uint64_t のフラグは l でいいのかとか.
あと, 実は g++ でも Windows だと危険だったりします.
No.7
- 回答日時:
> 素因数分解については理解できています
> なので10000を素因数分解するプログラムは作れるのですが、それ以下を判別して求めるプログラムは全くわかりません
と言うなら、まずはそのプログラムをどれかの補足に載せましょうよ。
素因数分解ができるなら、因子数もわかるでしょうから、あとはそれを比較する部分を書くだけです。
まずは素因数分解した時の因子数を数えるプログラムを書いてはいかがでしょうか。C言語で書くとしたら、素因数分解の結果を覚えておくメモリーの管理が面倒くさいはずなので、とりあえずそれは後回しにしましょう。
次に、因子数の最大値を求めるプログラムを書いてみましょう。
それから、後回しにしていた素因数分解した結果の記録と表示を作ってみましょう。
C言語で書くならなら、mainあたりで因子数が最大値を達成した時の値を覚えておく配列と各因数分解の時に使用する配列の2つを用意して、これまでの最大値を超える因子数が出るごとにコピーしておくとかになるでしょうね。長さを管理する変数をそれぞれに用意するか、それぞれの配列の最後に番兵として-1や0などを入れるかですね。(あるいは、単に2つ配列を用意し、作業用の配列を指すポインターとこれまでの最大値を超える因子数が出た時の配列を指すポインターを付け替えながら動作するか。)
10000以下の自然数なので、どんなに効率が悪いプログラムで現実的な時間で終わると思いますが、もしどうしても遅い場合は100などもう少し小さい数でプログラムを書いて、高速化方法を検討し、10000にチャレンジしましょう。
高速化で自分がまず思いつくのはエラトステネスの篩のように平方根までしか素因数分解のときに試さないというものです。
あと、再起を使ったプログラムを書いている場合、メモリーがある程度あり、メモリーの管理がかったるくないならメモ化も検討します。
ちなみに、以上のことをC++で書いてみるとこんな感じです。
#include <cmath>
#include <cstdio>
#include <unordered_map>
#include <vector>
using std::vector;
using std::printf;
std::unordered_map<uint64_t, vector<uint64_t> > memo;
vector<uint64_t>
factor(uint64_t num)
{
if (num < 2) { // i.e. 0, 1.
return vector<uint64_t>();
}
auto got = memo.find(num);
if (got != memo.end()) {
return got->second;
}
uint64_t max_div = static_cast<uint64_t>(std::sqrt(num));
for (uint64_t i = 2; i <= max_div; i++) {
if (num % i == 0) {
vector<uint64_t> result = factor(num / i);
result.push_back(i);
memo.emplace(num, result);
return result;
}
}
vector<uint64_t> ret;
ret.push_back(num);
memo.emplace(num, ret);
return ret;
}
int
main(void)
{
uint64_t max_value;
vector<uint64_t> max_factored;
for (uint64_t i = 2; i <= 10000; i++) {
vector<uint64_t> factored = factor(i);
if (factored.size() > max_factored.size()) {
max_value = i;
max_factored.swap(factored);
}
}
printf("%ld = ", max_value);
for (size_t i = 0; i < max_factored.size(); i++) {
if (i != 0) {
printf(" * ");
}
printf("%ld", max_factored[i]);
}
printf("\n#elms: %zd\n", max_factored.size());
return 0;
}
ちなみに、unordered_mapやautoを使っているので、C++11を理解しないコンパイラーだとコンパイルできません。-std=c++11をつけると対応したg++やclang++でコンパイルできると思います。
No.6
- 回答日時:
全部まとめてやろうとするから、わからなくなるのです。
「プログラム」を作ろうとするあら、わからなくなるのです。
・問題を細かくわけて考える
・まずは「やり方」を考える。その内容を「プログラミング言語で記述する」
というのがプログラミングのコツです。
素因数分解はできる、ということなら
1を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
2を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
3を素因数分解→因子数1→ 暫定最大値1,暫定最大因子数1
4を素因数分解→因子数2→ 暫定最大値4,暫定最大因子数2
5を素因数分解→因子数1→ 暫定最大値4,暫定最大因子数2
...
10000を素因数分解→因子数??→ 暫定最大値??,暫定最大因子数??
という「やり方」ができる、ということです。
これを「プログラミング言語で記述する」ことは簡単でしょう。
これでは効率が悪い、もっと効率よくしたい、という場合でも、まずは「やり方」を考えることです。
例えば
・素数は因子が1つしかないので最大値の候補とはならない
→最初に素数一覧を作れば、その一覧にあるものは候補から取り除ける
→効率のよい素数一覧作成方法は?
・8192=2^13で因子数13. log2(10000)=13.28....。ただの偶然でしょうか?
No.5
- 回答日時:
1の素因数分解をする
2の素因数分解をする
...
10000の素因数分解をする
その中で一番因子の数が多かったのはどれ?
という問題なんですから素因数分解理解してるのならできるんじゃ?
No.3
- 回答日時:
素因数分解の方法と再帰プログラムの基本さえ判ってれば30分もかからないで作れるね。
参考になるようにPHPで書いてみた。C言語が読めるならPHPでも読めるでしょう。
でも面倒なので因子数の最大を求めてない。出力フォーマットも合わせてない。
あくまでも参考にしてくださいな。
<?php
function decomposition ($val, $div, $cnt) {
if ($val==0 || $val==1) print "因子数 $cnt\n";
else if ($val % $div ==0) {
$cnt ++;
print $div.",";
decomposition ($val/$div, $div, $cnt) ;
}
else decomposition ($val, $div+1, $cnt) ;
}
for ($i=10; $i<10001; $i++) {
print "$i,";
decomposition ($i, 2, 0);
}
?>
出力(一部抜粋)
8192,2,2,2,2,2,2,2,2,2,2,2,2,2,因子数 13
No.1
- 回答日時:
> プログラムを作成して下さい
嫌です。
あなたのこの質問は何らかの課題の丸投げにしか見えません。
別に課題だから答えないというのではありません。あなたが悩んでここまでしかできなかったというコードと一緒に質問されたならば、私たち回答者は(少なくとも私は)あなたが悩んでいることについて喜んでアドバイスするでしょう。
しかし、丸投げの質問に対して答をポンと渡すと結局はその当人のプログラミング技術の向上のためにならないことを、プログラミング系の回答者は実体験などから身に染みて実感しています。
だから、ことプログラミング関係の質問の場で課題の丸投げは嫌われますし、私も嫌いです。
あなたがこの課題に対してどんなコードが書けたかを補足願います。
この回答への補足
素因数分解については理解できています
なので10000を素因数分解するプログラムは作れるのですが、それ以下を判別して求めるプログラムは全くわかりません
アドバイスしていただけると幸いです
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 【 数A 自然数の積と素因数の個数 】 2 2023/03/02 23:58
- 数学 整数問題 11 素数再びの再び 36 2023/04/29 14:59
- 数学 素数とか素因数分解、自然数を詳しくお願いします。 自然数ってお風呂って聞いたんですけど、どういうこと 7 2022/04/15 20:36
- 数学 中一数学の【最大公約数と最小公倍数】の問題です。 1問だけでも教えていただけると嬉しいです。 (1) 4 2022/08/01 10:19
- 数学 素因数分解は素数になったら辞めるはずなのに、 画像のようにルート24の素因数分解が2の2乗×6と、 5 2023/06/13 22:57
- 数学 x^p-1=(x-1)(x-ζ)(x-ζ^2)・・・(x-ζ^p-1)と複素数の中で因数分解できる理 1 2022/11/23 14:59
- 数学 これまでに愚かな回答者を何人も見てきました。 それでも私は問うてみたい。 京都大学の入試問題に 「 6 2023/05/01 14:06
- 数学 「素数」とは、「1と、それ自身でしか割り切れない数」。 「素因数分解」も「素数」の仲間ですか? 3 2022/04/14 22:45
- 数学 複素数の範囲での因数分解について。 ax^2+bx+c = a(x-α)(x-β)は 2つの解αβが 2 2022/08/19 08:29
- 数学 零因子(右零因子、左零因子)について 右零因子になるが、左零因子にならない。という例はありますか? 3 2022/04/19 09:26
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
360度を超える角度
-
Visual Basic 三辺の長さ? ...
-
main関数終了時のreturnの意味は?
-
3つの整数のうち奇数のみを表示...
-
Delphi 6 で 2進数→10進数変換
-
Fortran90についての質問です。
-
JCLの基本について教えてください
-
fortran if文
-
Sublime Text 3でのFortranプロ...
-
c言語です
-
変数の値が勝手に変化する原因
-
プログラミング
-
N88basicを用いたGPIB制御
-
4桁の数値を逆に表示されるプ...
-
あるプログラムのコマンドライ...
-
Excelで4096点以上のFFTの方法
-
このプログラミング誰か教えて...
-
65536は2の何乗なのでしょうか?
-
C++ で、「)」が必要 というエ...
-
正しい五十音順について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
プログラミング
-
【JAVA】数字をひし形に出力す...
-
変数の値が勝手に変化する原因
-
ruby
-
JCLの基本について教えてください
-
値Xを入力し、その平方根を画面...
-
N88basicを用いたGPIB制御
-
COBOLのピリオド
-
ProC 固定SQLでNULLってどう表...
-
Fortran90についての質問です。
-
main関数終了時のreturnの意味は?
-
360度を超える角度
-
C言語 バッファについて。
-
3つの整数のうち奇数のみを表示...
-
Fortran "実引数の型が仮引数の...
-
Delphi 6 で 2進数→10進数変換
-
javaで整数nを入力し、それが素...
-
fortran if文
-
3次関数を作るプログラム
-
BASICプログラム入門 副書名 プ...
おすすめ情報