スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ナップサック問題を動的計画法で解くCプログラムの例

ナップサック問題を動的計画法で解く C プログラムの例。

ナップサック問題とは、正の整数の列 v[0], v[1], ..., v[n-1] と w[0], w[1], ..., w[n-1]、および正の整数 W が与えられたとき、Σw[i] (i∈S) が W 以下という条件の下で Σv[i] (i∈S) が最大になる集合 S ⊆ { 0, 1, ..., n-1 } を求める問題です。

動的計画法は、最適化問題を解くためのボトムアップ的な手法です。与えられた問題を解く際、より小さいサイズの問題から順に解き、前段階の解を利用して次段階の解を求め、最終的にもとの問題の解を得ます。プログラムの動作においては、ある時点までの計算結果をメモリに記憶しておき、それを次の計算で再利用することにより、余分な計算を省いて効率化を図ります。

more...

スポンサーサイト

【theme : プログラミング
【genre : コンピュータ

中国式剰余定理のC言語によるプログラム例

中国式剰余定理の C 言語による素朴な実装の例。ここでいう「素朴」とは、Gauss の方法としてよく知られているアルゴリズムをそのままプログラムにしたという意味です。この記事では述べませんが、中国式剰余定理の実装においては、さまざまな効率化・高速化の方法があります。

more...

【theme : プログラミング
【genre : コンピュータ

Cornacchia-Smith法のC言語による実装例

奇素数 p と、p で割り切れない正整数 d に対して、方程式 p = x^2 + d * y^2 の整数解 (x, y) を計算するアルゴリズムである Cornacchia-Smith 法 の C 言語による実装例。

more...

【theme : プログラミング
【genre : コンピュータ

奇素数を法とする平方根を計算するCプログラムの例

奇素数を法とする平方根を、M. Cipolla によるアルゴリズムで計算する C プログラムの例。

more...

【theme : プログラミング
【genre : コンピュータ

法mに関する逆元を計算するCプログラムの例

互いに素な整数 a, m が与えられたとき、a * x = 1 mod m を満たす整数 x を計算する C プログラムの例。

more...

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。