@kagamiz (Jayson Sho Toma)

Slides:



Advertisements
Similar presentations
山元進.  for 文  while 文  do ~ while 文  文のネスト  break 文  continue 文.
Advertisements

コンピュータプラクティ スⅠ 比較実験 水野嘉明. 本日の予定 計算量について 「比較実験」  パラメータを変化させての比較 ⇒ 実験1  二つのプログラムの比較 ⇒ 実験2  実験レポート R3として提出 2.
C 言語講座第 5 回 構造体. 構造体とは ... 異なる型の値をまとめて新しい型とする 機能がある . つまり , 複数の変数を 1 つのまとまりにできる . 配列と違って同じ型でデータをまとめるのではな く違った型のデータをまとめられる .
素数判定の効率性について 東邦大学理学部情報科学科卒業研究発表会 指導教員 白柳 潔 提出者 後藤 雄大.
模擬国内予選2013 Problem F テトラ姫のパズル 原案:須藤 解答:大友、須藤 解説:須藤.
0章 数学基礎.
J: Magical Switches JAG 模擬地区予選 2013 原案:保坂 解答:保坂・楠本 解説:保坂.
初年次セミナー 第8回 データの入力.
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
アルゴリズムイントロダクション第2章 主にソートに関して
情報・知能工学系 山本一公 プログラミング演習Ⅱ 第4回 配列(2) 情報・知能工学系 山本一公
アルゴリズムとデータ構造 第8回 ソート(3).
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
ファーストイヤー・セミナーⅡ 第8回 データの入力.
6/19 前回復習 for文による繰り返し計算 演習1:1から10まで足して画面に結果を表示する 提出者: 1人
6/26 前回復習 for文、while文による繰り返し計算
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
アルゴリズムイントロダクション第5章( ) 確率論的解析
アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015.
1. アルゴリズムと計算量.
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
6学年 算数 ~ 式 と 計 算 ~.
全体ミーティング (6/13) 村田雅之.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
データ構造とアルゴリズム論 第2章 配列(構造)を使った処理
Cygwin の install.
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
7.時間限定チューリングマシンと   クラスP.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング応用 printfと変数.
最適化の方法 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第11章.
正規分布確率密度関数.
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
わんくま同盟茶藝部顧問 Microsoft MVP for VC episthmh
クイックソート.
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
レッツ 学級会 オリエンテーション やってみよう コンテンツの操作方法 クリック クリック クリック.
プログラミング 4 探索と計算量.
配列変数とポインタ 静的確保と動的確保 ポインタ配列 2次元配列 時間計測 第1回レポートの課題
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
メールとネットワークセキュリティ           グループ:Seven Star.
計算機プログラミングI 第6回 2002年11月14日(木) アルゴリズムと計算量 第1回課題の説明 平方根を計算するアルゴリズム 計算量
香川大学創造工学部 富永浩之 情報数学1 第1-3章 素数と素因数分解 香川大学創造工学部 富永浩之
補講:アルゴリズムと漸近的評価.
データの表現 2進数 0と1を使う。 基数(基準になる数)が2. 101(2) かっこで2進数と示すことがある。
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
プログラミングⅡ 第2回.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
精密工学科プログラミング基礎 第7回資料 (11/27実施)
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
ヒープソート.
博士たちの愛する組合せ論 徳山 豪 東北大学 Combinatorics that professors love
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
参考:大きい要素の処理.
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
第7章 そろそろ int 以外も使ってみよう! ~データ型 double , bool~
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
プログラミング入門2 第5回 配列 変数宣言、初期化について
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
知能情報工学演習I 第10回( C言語第4回) 課題の回答
情報処理Ⅱ 第8回:2003年12月9日(火).
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
プログラミング論 バイナリーサーチ 1.
ファーストイヤー・セミナーⅡ 第10回 if文による選択処理(2).
Presentation transcript:

@kagamiz (Jayson Sho Toma) 講義 1: 素数と累積和 @kagamiz (Jayson Sho Toma)

素数とは? 1 とその数自身以外に約数を持たない数 ただし 1 は素数ではない なぜか考えてみよう 素数ではない数を合成数という

素数判定 数 n が素数かどうか判定したい 試し割りをしていく方法 素数の性質を使う方法 最悪 n に比例する時間がかかる

素数判定 数 n が素数かどうか判定したい 試し割りをしていく方法 素数の性質を使う方法 √nまでの素数で試し割りを行う 何故これでいいのか?

√n までの試し割り:証明 n が合成数であれば, 定義より n = a × b と表せる. いま a ≧ b ⇒ a × b ≧ b × b = b^2. よって n ≧ b^2, √n ≧ b となり, √n 以下の約数があることが証明された.//

実行時間とプログラムの計算量 ループの回数が大体 10^8 (1 億) で 1 秒 10^9 回の処理は約 10 秒程度かかる! 10^8 回以下程度の処理を心がけよう 詳しい話は「計算量 オーダー記法」で  ググる or 先輩達に聞こう

素数の個数を数える 区間 [l, r] の素数の個数を数えよう! [l, r] の素数を試し割りで毎回数えると, √l + √(l + 1) + … + √r ≦ (r – l + 1)√r [1, 10^6] の素数を試し割りで数えると, 10^9 回くらいの計算に 実際はもっと速いため KCS でもこれで OK

素数の個数を数える 効率的に数える方法として, エラトステネスの篩が有名 今回は, 複数の[l, r] のクエリに早く答える 詳しくは先輩たちに聞く or ググる 今回は, 複数の[l, r] のクエリに早く答える 方法を考えていこう.

高速化のアイディア 1 : 前計算 エラトステネスの篩を用いれば勝手に 前計算がされている. ・試し割りをしている人は, 配列を用意して  前計算がされている. ・試し割りをしている人は, 配列を用意して p が素数だったら 配列の p 番目の 要素を 1 にしよう

高速化のアイディア2:累積和 刮目せよ!!! さっき作った配列を… 1

高速化のアイディア2:累積和 刮目せよ!!! さっき作った配列を… 1

高速化のアイディア2:累積和 刮目せよ!!! さっき作った配列を… 右に足していく 1 1 2 3

高速化のアイディア2:累積和 1 2 3 4 5 6 この配列があると何が嬉しいか? 考えてみよう! 1 2 3