ユークリッドの互除法 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Euclidean algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針につい
素数判別、素因数分解＜アルゴリズム＜Ｗｅｂ教材＜木暮
学習のポイント 素数判別、素因数分解の基本的なアルゴリズムを理解します。 キーワード アルゴリズム、素数、剰余、素数判別、エラトステネスのふるい、素因数分解 これまでは、素数研究が社会に直接関係することはあまりありませんでした。ところが、電子メールなどの暗号化が必要になりました。その暗号鍵、復号鍵では、「非常に大きいを素因数分解する計算には非常に時間がかかる」ことをベースにしています（→参考：「公開鍵暗号方式の原理」）。そのため、素数に関する関心が高まっているのです。 ２，３，５，７，１１，１３，１７，…など、１と自分自身でしか割り切れない数を素数といいます。１２＝４×３や、１８＝２×９のように、素数ではない数のことを合成数といい、２、３、４、９など、合成数を割り切れる数を約数といいます。そして、２や３など約数自体が素数であるとき、その約数を素因数といいます。 素数を扱うアルゴリズムは、大
ユークリッドの互除法 - inamori’s diary
ユークリッドの互除法（Euclidean algorithm）は、最大公約数を求めるためのアルゴリズムです。 割り切れるまで割り算を繰り返します。例えば、234と177の最大公約数を求めるには、 234 ÷ 177 = 1 余り 57 177 ÷ 57 = 3 余り 6 57 ÷ 6 = 9 余り 3 6 ÷ 3 = 2 余り 0 だから、最大公約数は3となります。 コードは、再帰を使って書くと簡単です。Cで書くと、 #include int GCD_core(int a, int b) { int d = a % b; if(d == 0) return b; else return GCD_core(b, d); } int GCD(int a, int b) { /* Pythonの仕様に合わせてある */ if(a == 0) return b; else if(b == 0) r
互いに素 - inamori’s diary
互いに素（coprime）とは、与えられた2つの整数が共通の素因数を持たないことを意味します。 例えば、4と6なら、 4 = 22 6 = 2•3 だから、2が共通の素因数となり、互いに素ではありません。12と25なら、 12 = 22•3 25 = 52 だから、互いに素です。 プログラムでこれを調べたいときは、最大公約数が1かどうかを調べます。1なら互いに素、そうでなければ互いに素でないことになります（負数を扱うときは注意）。 互いに素は、Project Eulerを解いていても意外とよく出てくる概念です。例えば、辺の長さがa, b, cの三角形を考えるとき、これらが互いに素でなければ、最大公約数で割った辺の長さの三角形と相似なので、こちらだけ考えればよい、などというように使われます。 関連 ユークリッドの互除法
順列 - Wikipedia
この項目では、順列について説明しています。初等組合せ論における permutationについては「置換」をご覧ください。 数え上げ数学における順列（じゅんれつ、英: sequence without repetition, partial permutation、仏: arrangement）は、区別可能な特定の元から有限個を選んで作られる重複の無い列をいう[1]。 初等組合せ論における「写像12相」はともに 有限集合から k-個の元を取り出す方法として可能なものを数え上げる問題に関するものである[2]。取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。 定義 1 位数 n の有限集合 E と自然数 k に対し、E の元からなる k-順列とは {1, 2, …, k} から E への単射を言う。 定義 2 位数 n の有限集合 E と自然数 k に対し、E の元か
決定的アルゴリズム - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "決定的アルゴリズム" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年3月) 決定的アルゴリズム（けっていてきアルゴリズム、英: deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。 決定的アルゴリズムは
乱択アルゴリズム - Wikipedia
乱択アルゴリズム（らんたくアルゴリズム）、ランダム・アルゴリズム（英: randomized algorithm）または確率的アルゴリズム（かくりつてきアルゴリズム、（英: probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的とすることがある。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を期待実行時間[1]と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。 n 個の要素からなる配列から「a」という要素を探す問題を考える。この配列の各要素は半分が「a」で残りが「b」である。単純
DirectXの話 第88回 「球面調和関数」
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
Summed-area table - Wikipedia
Using a summed-area table (2.) of a 6×6 matrix (1.) to sum up a subrectangle of its values; each coloured spot highlights the sum inside the rectangle of that colour. A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. In the image processing domain, it is also known as an integral image. It was introduce
微分方程式を解こう！ | _level0 - KAYAC Front Engineer Blog
どうも。こんにちは。梅雨明けも宣言されたそうで、いよいよ暑くなりますね。今回は単振動方程式方程式を用いた最適化のお話です。 高校物理でも登場するバネの方程式、単振動方程式 を簡単な四則計算に分解する方法を紹介します。 まず色々な数学的背景を押しやって、イメージだけ説明すると、物体の位置x、速度v、加速度aの関係は となるので、asの式で考えると、 v += a; x += v; という風になります。ここで単振動の微分方程式から、 a = -K * x; であるから、あわせると、 v -= K * x; x += v; という風になります。下がサンプルで、初期値(_v, _y)やKなんかを変えて挙動が変わることが分かります。 ここでのポイントはvに対して最初の式で破壊的な操作を行っていることです。 v_temp = v; v -= K * x; x += v_temp; 等とすると、ずれてし
凸集合 - Wikipedia
円板のように見える凸集合、（緑色）の凸集合は x と y を繋ぐ（黒色）の直線部分を含んでいる。凸集合の内部に直線の部分の全体が含まれる。 ブーメランのように見える非凸集合、x と y を繋ぐ（黒色）の直線の一部が（緑色）の非凸集合の外側へはみ出ている。 ユークリッド空間における物体が凸（とつ、英: convex）であるとは、その物体に含まれる任意の二点に対し、それら二点を結ぶ線分上の任意の点がまたその物体に含まれることを言う。例えば中身のつまった立方体は凸であるが、例えば三日月形のように窪みや凹みのあるものは何れも凸でない。凸曲線（英語版）は凸集合の境界を成す。 凸集合の概念は後で述べるとおり他の空間へも一般化することができる。 函数が凸であることと、函数のグラフの（緑色の）領域が函数のグラフの上にあるような函数は（下に）凸である。 S は実数体（あるいはより一般に適当な順序体）上のベク
wonderfl build flash online | 面白法人カヤック
wonderflは、サイト上でFlashをつくることのできるサービス。 通常Flashをつくるためには、Flash IDEやFlex、FlashDevelop等といったツールを使って、コードを書き、コンパイルする必要がありますが、wonderflでは、サイトにあるフォームにActionscript3のコードを書けば、サーバサイドでコンパイルを行えます。 つまり、ブラウザさえあれば、Flashをつくれます。コンパイル結果はサイト上に表示され、作成されたFlash（swf）はページ上に自動的に表示されるので、完成したFlashをリアルタイムに見ながらコードを書くことができます。 ※APIとして、はてな OpenIDを使用してネットにさえつながれば、誰もがFlashクリエイターになれます。世界中のFlashクリエイターがユーザーになるwonderflは、 文字通り、世界のFlash図鑑となってい
Minimum bounding rectangle - Wikipedia
A series of geometric shapes enclosed by its minimum bounding rectangle In computational geometry, the minimum bounding rectangle (MBR), also known as bounding box (BBOX) or envelope, is an expression of the maximum extents of a two-dimensional object (e.g. point, line, polygon) or set of objects within its x-y coordinate system; in other words min(x), max(x), min(y), max(y). The MBR is a 2-dimens
Minimum bounding box - Wikipedia
A sphere enclosed by its axis-aligned minimum bounding box (in 3 dimensions) In geometry, the minimum bounding box or smallest bounding box (also known as the minimum enclosing box or smallest enclosing box) for a point set S in N dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure are used
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
2の冪 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "2の冪" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年6月) 2の冪 2n の直方体による図示。 左上1 (=20) から右下 1024 (=210) まで。 2の冪（にのべき、（英: power of two）は、2 を底とし整数の指数を持つ冪である。2の冪は、指数を n として一般に、2n の形で表される（例えば n = 0, 1, 2, 3, … に対してそれぞれ 20 = 1, 21 = 2, 22 = 4, 23 = 8, …）。 1に2倍のみを繰り返すことによって得られる数であり、ごく基本的な数量操作で得られる
スターリングの近似 - Wikipedia
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。 脚注を導入して、記事の信頼性向上にご協力ください。（2015年12月） log n! と n log n − n は n → ∞ のとき漸近する スターリングの近似（英: Stirling's approximation）またはスターリングの公式（英: Stirling's formula）は、階乗、あるいはその拡張の一つであるガンマ関数の漸近近似である。名称は数学者ジェイムズ・スターリング（英語版）にちなむ。 スターリングの近似は精度に応じていくつかの形がある。応用上よく使われる形の公式は、ランダウの記号を用いて、 である。O(log n) における次の項は (1/2)log 2πn である。故に、次によい近似の漸近公式（英語版）は である[1]。（ここで記号 は両辺の比が（n
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Erlang: 組合せをやってみる | | プログラマ2.0日報 | あすなろBLOG
単調増加関数とは何か？
Lua/組み込み - assari