@okuraofvegetabl
|
|
|
- まれあ てっちがわら
- 5 years ago
- Views:
Transcription
1 @okuraofvegetabl
2
3 3 I 5 1? , II 15 1 Bellman-Ford( ) Dijkstra( ) Warshall-Floyd( ) III, 25 1, IV
4
5 I okuraofvegetable "TopCoder" "Codeforces" "AtCoder"( ) C++ int long long int 1? (node) (edge) V, E G = (V, E) u, v e(u, v) ( ) 5
6 I I.1 2 e(u, v) u v v u e(u, v) u v (u, v) (v, u) e(u, v) e u, v u e v e v v, v 3, V E G(V,E) P (V, E ) V V, E E 6
7 I I.2 I.3 2 u,v ( ) u u 7
8 I I path (path) (path) P (V, E), V = v 0, v 1, v k,e = v 0 v 1, v 1 v 2, v k 1 v k (v p v q e(v p, v q ) ) v 0, v 1 v k P = v 0 v 1 v k (cycle) P=v 0 v k 1 path k 3 C := P +v k 1 v 0 path 8
9 I I.5 I.6 2 u,v path ( ) ( ) ( ) 9
10 I I.7 I.8 DAG DAG DAG(Directed Acyclic Graph) 10
11 I I.9 DAG DAG 4 node V V graph[i] [j] e(i, j) O(1) V 11
12 I 2 C++ vector O( V + E ) V PKU Online Judge vector TLE vector N, M 2 (u, v) Q u v "YES", "NO" ( 0 N 1 1 N,M,Q M (a 0, b 0 ) (a m 1, b m 1 ) a i b i Q (u 0, v 0 ) (u q 1, v q 1 ) ) : 0 N 1000, 0 M N(N 1)/2, 0 Q Time Limit 1sec, Memory Limit 64MB N 1000 O(NQ) # include <cstdio> # include <cstring> bool graph[1050][1050]; int main() int N,M,Q; memset(graph,false,sizeof(graph)); scanf("%d %d %d",&n,&m,&q); for(int i=0;i<m;i++) 12
13 I int a,b; scanf("%d %d",&a,&b); graph[a][b]=true; for(int i=0;i<q;i++) int u,v; scanf("%d %d",&u,&v); if(graph[u][v])printf("yes\n"); else printf("no\n"); return 0; # include <cstdio> # include <vector> std::vector<int> graph[1050]; int main() int N,M,Q; scanf("%d %d %d",&n,&m,&q); for(int i=0;i<m;i++) int a,b; scanf("%d %d",&a,&b); graph[a].push_back(b); for(int i=0;i<q;i++) int u,v; scanf("%d %d",&u,&v); for(int j=0;j<graph[u].size();j++) if(graph[u][j]==v) 13
14 I printf("no\n"); end:; return 0; printf("yes\n"); goto end; 14
15 II u v path 1 Bellman-Ford( ) 1 i s d [i] d [i] = mind [j] + e(j, i) e(j, i) E d [s] = 0, d [i] = INF ( ) s V 1 V O( V E ) "Negative loop exists." s ( INF ) # include <cstdio> # include <vector> # include <algorithm> using namespace std; # define INF # define MAX_V
16 II int V;//number of vertices struct edgeint from,to,cost;; vector<edge> edges; int d[max_v]; int main() fill(d,d+v,inf); int s; scanf("%d",&s); d[s]=0; for(int i=0;i<v;i++) for(int j=0;j<edges.size();j++) edge e=edges[j]; if(d[e.to]>d[e.from]+e.cost) d[e.to]=d[e.from]+e.cost; if(i==v-1) printf("negative loop exists.\n"); return 0; for(int i=0;i<v;i++)printf("%d\n",d[i]); return 0; 2 Dijkstra( ) 1 2 Dijkstra 16
17 II d [s] = 0, d [i] = INF 1. d [i] 2. V ( ) S P P d [i] = mind [j] j P i, d [i] s s i path d [i] path s P k d [k] d [i] path d [i] d [i] V O( V 2 ) (priority queue) O(log V ) O( E log V ) ( ) s dijkstra s ( INF ) graph index, O( V 2 ) # include <cstdio> # include <cstring> # include <algorithm> # include <vector> # define INF
18 II # define MAX_V using namespace std; int V;//number of vertices int d[max_v]; bool used[max_v]; struct edgeint to,cost;; vector<edge> graph[max_v]; void dijkstra(int s) fill(d,d+v,inf); memset(used,false,sizeof(used)); d[s]=0; for(int i=0;i<v;i++) int id; for(int j=0;j<v;j++)if(!used[j]&&d[id]>d[j])id=j; used[id]=true; for(int j=0;j<graph[id].size();j++) edge e=graph[id][j]; d[e.to]=min(d[e.to],d[id]+e.cost); return; int main() int s; scanf("%d",&s);//0-indexed dijkstra(s); for(int i=0;i<v;i++)printf("%d\n",d[i]); return 0; O( E log V ) 18
19 II # include <cstdio> # include <cstring> # include <functional> # include <queue> # include <utility> # include <vector> using namespace std; typedef pair<int,int> P; # define mp make_pair # define MAX_V # define INF int V; int d[max_v]; struct edgeint to,cost;; vector<edge> graph[max_v]; void dijkstra(int s) fill(d,d+v,inf); d[s]=0; priority_queue<p,vector<p>,greater<p> > q; q.push(mp(0,s));//(distance,index) while(!q.empty()) P a=q.top(); q.pop(); if(d[a.second]<a.first)continue; for(int i=0;i<graph[a.second].size();i++) edge e=graph[a.second][i]; if(d[e.to]>d[a.second]+e.cost) d[e.to]=d[a.second]+e.cost; q.push(mp(d[e.to],e.to)); return; 19
20 II int main() int s; scanf("%d",&s); dijkstra(s); for(int i=0;i<v;i++)printf("%d\n",d[i]); return 0; 3 Warshall-Floyd( ) DP( ) dp [k + 1] [i] [j] := 0 k, i, j i j path k + 1 = 0 i j path e(i, j) ( INF) 0 k i,j path k 2 dp [k + 1] [i] [j] = dp [k] [i] [j] path i k, k j dp [k + 1] [i] [j] = dp [k] [i] [k] + dp [k] [k] [j] dp [k + 1] [i] [j] = min(dp [k] [i] [j], dp [k] [i] [k] + dp [k] [k] [j]) dp [k + 1] [i] [j] (i, j ) dp [k] [i] [j] dp [V ] [i] [j] O( V 3 ) Time Limit 1 sec V ( 2 O(1) ) # include <algorithm> using namespace std; # define MAX_V 500 int V;//number of vertices int dp[max_v][max_v]; //if e(u,v) exists,d[u][v]=cost of e(u,v) 20
21 II //otherwise,d[u][v]=inf(but if i=j,dp[i][i]=0) void warshallfloyd() for(int k=0;k<v;k++) for(int i=0;i<v;i++) for(int j=0;j<v;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]); return; int main() warshallfloyd(); return 0; (to) (from) i j i j ( ) d [i] + e(i, j) d [j] (d s ) d d [i] s i LP( ) ( )! PKU 3169 Lay out d [i] i d [i] d [i + 1] (AL,BL,DL) d [AL] + DL d [BL], (AD,BD,DD) d [AD] + DD d [BD] d d [N] d [1] i + 1 i 0 AL BL DL BD AD DD 21
22 II 1 N # include <cstdio> # include <algorithm> # include <vector> using namespace std; # define INF struct edge int from,to,cost; edge(int f,int t,int c):from(f),to(t),cost(c) ; vector<edge> edges; int d[1050]; int N,ML,MD; int main() scanf("%d %d %d",&n,&ml,&md); for(int i=1;i<n;i++) edge in(i,i-1,0); edges.push_back(in); for(int i=0;i<ml;i++) int AL,BL,DL; scanf("%d %d %d",&al,&bl,&dl); AL--;BL--;//1...N -> 0...N-1 edge in(al,bl,dl); edges.push_back(in); for(int i=0;i<md;i++) int AD,BD,DD; 22
23 II scanf("%d %d %d",&ad,&bd,&dd); AD--;BD--; edge in(bd,ad,-dd); edges.push_back(in); fill(d,d+n,inf); d[0]=0; for(int i=0;i<n;i++) for(int j=0;j<edges.size();j++) edge e=edges[j]; if(d[e.to]>d[e.from]+e.cost) d[e.to]=d[e.from]+e.cost; if(i==n-1) //negative loop exists printf("-1\n"); return 0; if(d[n-1]==inf) //can t arrive at N-1 printf("-2\n"); return 0; printf("%d\n",d[n-1]); return 0; " " 23
24
25 III, 1, ( ) III.1 25
26 III, III.2 DFS (DFS/Depth-First Search) DFS DFS DFS 26
27 III, III.3 DFS ( ) ( ) DFS (DFS Tree) DFS (backward edge) 2 lowlink lowlink DFS (ord) v lowlink v DFS ord lowlink 27
![III, ord,lowlink ord,lowlink DFS # include <vector> # include <algorithm> using namespace std; # define MAX_V 10000 vector<int> graph[max_v]; bool](/docs-images/94/120480383/images/28-1.jpg "used_v[max_v],used_e[max_v][max_v]; int ord[max_v],lowlink[max_v]; int k=0; void dfs(int v) used_v[v]=true; ord[v]=lowlink[v]=k++; for(int i=0;i<graph[v].")
28 III, ord,lowlink ord,lowlink DFS # include <vector> # include <algorithm> using namespace std; # define MAX_V vector<int> graph[max_v]; bool used_v[max_v],used_e[max_v][max_v]; int ord[max_v],lowlink[max_v]; int k=0; void dfs(int v) used_v[v]=true; ord[v]=lowlink[v]=k++; for(int i=0;i<graph[v].size();i++) 28
29 III, return; if(!used_v[graph[v][i]]) used_e[v][graph[v][i]]=true; dfs(graph[v][i]); lowlink[v]=min(lowlink[v],lowlink[graph[v][i]]); else if(!used_e[graph[v][i]][v]) //then,e(v,graph[v][i]) is backward edge lowlink[v]=min(lowlink[v],ord[graph[v][i]]); lowlink ord,lowlonk ord DFS DFS ord ord e(u, v)(u v ) DFS v 2 2 e(u, v) e(u, v) lowlink v DFS ord e(u, v) ord [u] < lowlink [v] ord,lowlink O(1) ord,lowlink DFS O( V ), O( E ) O( V + E ) ord lowlink DFS (DFS ) 1 29
30 III, v v v v u lowlink [u] > ord [v] v lowlink v v v ord [u] lowlink [v] v u O( V + E ) 30
31 IV Online 31
32
33 [1] R. (,2012) [2],, 2 (,2010) 33
@okuraofvegetabl
@okuraofvegetabl 3 I 5 II 7 1.................................... 7 2............................... 10 3................................... 10 4............................ 21 III 29 1 Propagating tree
Ｃ言語によるアルゴリズムとデータ構造
Algorithms and Data Structures in C 4 algorithm List - /* */ #include List - int main(void) { int a, b, c; int max; /* */ Ÿ 3Ÿ 2Ÿ 3 printf(""); printf(""); printf(""); scanf("%d", &a); scanf("%d",
main
14 1. 12 5 main 1.23 3 1.230000 3 1.860867 1 2. 1988 1925 1911 1867 void JPcalendar(int x) 1987 1 64 1 1 1 while(1) Ctrl C void JPcalendar(int x){ if (x > 1988) printf(" %d %d \n", x, x-1988); else if(x
「産業上利用することができる発明」の審査の運用指針（案）
1 1.... 2 1.1... 2 2.... 4 2.1... 4 3.... 6 4.... 6 1 1 29 1 29 1 1 1. 2 1 1.1 (1) (2) (3) 1 (4) 2 4 1 2 2 3 4 31 12 5 7 2.2 (5) ( a ) ( b ) 1 3 2 ( c ) (6) 2. 2.1 2.1 (1) 4 ( i ) ( ii ) ( iii ) ( iv)
C のコード例 (Z80 と同機能 ) int main(void) { int i,sum=0; for (i=1; i<=10; i++) sum=sum + i; printf ("sum=%d n",sum); 2
アセンブラ (Z80) の例 ORG 100H LD B,10 SUB A LOOP: ADD A,B DEC B JR NZ,LOOP LD (SUM),A HALT ORG 200H SUM: DEFS 1 END 1 C のコード例 (Z80 と同機能 ) int main(void) { int i,sum=0; for (i=1; i
( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1
![( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1](/thumbs/96/128219471.jpg "( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1")
() 2006 2 27 1 10 23 () 30 () 27 [1] p.97252 7 2 2.1 2.1.1 1 LIFO(last in first out, ) (push) (pup) 1 1: 2.1.2 1 List 4-1(p.100) stack[] stack top 1 2 (push) (pop) 1 2 void stack push(double val) val stack
I. Backus-Naur BNF S + S S * S S x S +, *, x BNF S (parse tree) : * x + x x S * S x + S S S x x (1) * x x * x (2) * + x x x (3) + x * x + x x (4) * *
2015 2015 07 30 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1 I. Backus-Naur BNF S + S S * S S x S +, *, x BNF S (parse tree) : * x + x x S * S x + S S S x x (1) * x x * x (2) * + x x x (3) +
44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)
(1) I 44 II 45 III 47 IV 52 44 4 I (1) ( ) 1945 8 9 (10 15 ) ( 17 ) ( 3 1 ) (2) 45 II 1 (3) 511 ( 451 1 ) ( ) 365 1 2 512 1 2 365 1 2 363 2 ( ) 3 ( ) ( 451 2 ( 314 1 ) ( 339 1 4 ) 337 2 3 ) 363 (4) 46
i ii i iii iv 1 3 3 10 14 17 17 18 22 23 28 29 31 36 37 39 40 43 48 59 70 75 75 77 90 95 102 107 109 110 118 125 128 130 132 134 48 43 43 51 52 61 61 64 62 124 70 58 3 10 17 29 78 82 85 102 95 109 iii
I. Backus-Naur BNF : N N 0 N N N N N N 0, 1 BNF N N 0 11 (parse tree) 11 (1) (2) (3) (4) II. 0(0 101)* (
2016 2016 07 28 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1 I. Backus-Naur BNF : 11011 N N 0 N N 11 1001 N N N N 0, 1 BNF N N 0 11 (parse tree) 11 (1) 1100100 (2) 1111011 (3) 1110010 (4) 1001011
4 5 6 CHAPTER 1 1 1-1 n % i n = 3 m = 10 k = {1, 3, 5 Yes 1, 1, 3, 5 10 n = 3 m = 9 k = {1, 3, 5 No 9 8 1-1 #include const int MAX_N = 50; int main() { int n, m, k[max_n]; // scanf("%d %d", &n,
:30 12:00 I. I VI II. III. IV. a d V. VI
2017 2017 08 03 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1 I. Backus-Naur BNF X [ S ] a S S ; X X X, S [, a, ], ; BNF X (parse tree) (1) [a;a] (2) [[a]] (3) [a;[a]] (4) [[a];a] : [a] X 2 222222
(search: ) [1] ( ) 2 (linear search) (sequential search) 1
![(search: ) [1] ( ) 2 (linear search) (sequential search) 1](/thumbs/97/131825822.jpg "(search: ) [1] ( ) 2 (linear search) (sequential search) 1")
2005 11 14 1 1.1 2 1.2 (search:) [1] () 2 (linear search) (sequential search) 1 2.1 2.1.1 List 2-1(p.37) 1 1 13 n
:30 12:00 I. I VI II. III. IV. a d V. VI
2018 2018 08 02 10:30 12:00 I. I VI II. III. IV. a d V. VI. 80 100 60 1 I. Backus-Naur BNF N N y N x N xy yx : yxxyxy N N x, y N (parse tree) (1) yxyyx (2) xyxyxy (3) yxxyxyy (4) yxxxyxxy N y N x N yx
ALG2012-C.ppt
2012717 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html 1 1. 2. 2 .. 3 public class WeightedNode { private E value; // private Map
(STL) STL 1 (deta structure) (algorithm) (deta structure) 2 STL STL (Standard Template Library) 2.1 STL STL ( ) vector<int> x; for(int i = 0; i < 10;
(STL) STL 1 (deta structure) (algorithm) (deta structure) 2 STL STL (Standard Template Library) 2.1 STL STL ( ) vector x; for(int i = 0; i < 10; ++i) x.push_back(i); vector STL x.push_back(i) STL
LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1
2007 7 17 2 1 1.1 LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP 2 2 5 5 5 1: 1 2 データの追加 データの取り出し 5 2 5 2 5 2: 1.2 [1] pp.199 217 2 (binary tree) 2 2.1 (three: ) ( ) 秋田高専 校長 準学士課程学生
void hash1_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; /* i EMPTY */ void hash1_insert(int *array, int n) if (n < 0 n >=
![void hash1_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; /* i EMPTY */ void hash1_insert(int *array, int n) if (n < 0 n >=](/thumbs/89/97513163.jpg "void hash1_init(int *array) int i; for (i = 0; i < HASHSIZE; i++) array[i] = EMPTY; /* i EMPTY */ void hash1_insert(int *array, int n) if (n < 0 n >=")
II 14 2018 7 26 : : proen@mm.ics.saitama-u.ac.jp 14,, 8 2 12:00 1 O(1) n O(n) O(log n) O(1) 32 : 1G int 4 250 M 2.5 int 21 2 0 100 0 100 #include #define HASHSIZE 100 /* */ #define NOTFOUND 0
86 7 I ( 13 ) II ( )
10 I 86 II 86 III 89 IV 92 V 2001 93 VI 95 86 7 I 2001 6 12 10 2001 ( 13 ) 10 66 2000 2001 4 100 1 3000 II 1988 1990 1991 ( ) 500 1994 2 87 1 1994 2 1000 1000 1000 2 1994 12 21 1000 700 5 800 ( 97 ) 1000
e /5/21( )
e05577 008/5/( ) (Depth First Search Tree) 3. node............................ 3. getnodeid getnodename................... 3.3.......................... 4.4................... 5.4. (articulation point)............
C による数値計算法入門 ( 第 2 版 ) 新装版 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 新装版 1 刷発行時のものです.
C による数値計算法入門 ( 第 2 版 ) 新装版 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/009383 このサンプルページの内容は, 新装版 1 刷発行時のものです. i 2 22 2 13 ( ) 2 (1) ANSI (2) 2 (3) Web http://www.morikita.co.jp/books/mid/009383
i
14 i ii iii iv v vi 14 13 86 13 12 28 14 16 14 15 31 (1) 13 12 28 20 (2) (3) 2 (4) (5) 14 14 50 48 3 11 11 22 14 15 10 14 20 21 20 (1) 14 (2) 14 4 (3) (4) (5) 12 12 (6) 14 15 5 6 7 8 9 10 7
[ 1] 1 Hello World!! 1 #include <s t d i o. h> 2 3 int main ( ) { 4 5 p r i n t f ( H e l l o World!! \ n ) ; 6 7 return 0 ; 8 } 1:
![[ 1] 1 Hello World!! 1 #include <s t d i o. h> 2 3 int main ( ) { 4 5 p r i n t f ( H e l l o World!! \ n ) ; 6 7 return 0 ; 8 } 1:](/thumbs/97/132863283.jpg "[ 1] 1 Hello World!! 1 #include <s t d i o. h> 2 3 int main ( ) { 4 5 p r i n t f ( H e l l o World!! \ n ) ; 6 7 return 0 ; 8 } 1:")
005 9 7 1 1.1 1 Hello World!! 5 p r i n t f ( H e l l o World!! \ n ) ; 7 return 0 ; 8 } 1: 1 [ ] Hello World!! from Akita National College of Technology. 1 : 5 p r i n t f ( H e l l o World!! \ n ) ;
‚æ4›ñ
( ) ( ) ( ) A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 (OUS) 9 26 1 / 28 ( ) ( ) ( ) A B C D Z a b c d z 0 1 2 9 (OUS) 9
第１部 一般的コメント
(( 2000 11 24 2003 12 31 3122 94 2332 508 26 a () () i ii iii iv (i) (ii) (i) (ii) (iii) (iv) (a) (b)(c)(d) a) / (i) (ii) (iii) (iv) 1996 7 1996 12
O(N) ( ) log 2 N
2005 11 21 1 1.1 2 O(N) () log 2 N 1.2 2 1 List 3-1 List 3-3 List 3-4? 3 3.1 3.1.1 List 2-1(p.70) 1 1 10 1 3.1.2 List 3-1(p.70-71) 1 1 2 1 2 2 1: 1 3 3.1.3 1 List 3-1(p.70-71) 2 #include stdlib.h
cpp2.dvi
2018 c 2 C++ (2) STL, C++ 21 string 22 STL 23 21 string C, \0, (, ), (, ), /,,,, C++,,, string string,,,,,, include,,, int, > >>,,,, getline(, string ), [List 21] 2: #include 3: 4:
問題 01 水道料金を節約しよう 問題のポイント問題文で述べられた仕様を理解し その通りに動作するプログラムを記述できるかを問う問題です 変数 入出力 四則演算に加え 条件分岐や繰り返し処理についての知識が必要です 問題の解き方いくつかのアルゴリズムが考えられますが w が 100 以下と小さい値な
問題 01 水道料金を節約しよう 問題のポイント問題文で述べられた仕様を理解し その通りに動作するプログラムを記述できるかを問う問題です 変数 入出力 四則演算に加え 条件分岐や繰り返し処理についての知識が必要です 問題の解き方いくつかのアルゴリズムが考えられますが w が 100 以下と小さい値なので 水量を 1m 3 ずつ増やして料金を加算していく簡単なアルゴリズムでも大丈夫です 具体的には 使用水量
第１章 国民年金における無年金
1 2 3 4 ILO ILO 5 i ii 6 7 8 9 10 ( ) 3 2 ( ) 3 2 2 2 11 20 60 12 1 2 3 4 5 6 7 8 9 10 11 12 13 13 14 15 16 17 14 15 8 16 2003 1 17 18 iii 19 iv 20 21 22 23 24 25 ,,, 26 27 28 29 30 (1) (2) (3) 31 1 20
表1票4.qx4
iii iv v 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 22 23 10 11 24 25 26 27 10 56 28 11 29 30 12 13 14 15 16 17 18 19 2010 2111 22 23 2412 2513 14 31 17 32 18 33 19 34 20 35 21 36 24 37 25 38 2614
新・明解Ｃ言語で学ぶアルゴリズムとデータ構造
第 1 章 基本的 1 n 141 1-1 三値 最大値 algorithm List 1-1 a, b, c max /* */ #include int main(void) { int a, b, c; int max; /* */ List 1-1 printf("\n"); printf("a"); scanf("%d", &a); printf("b"); scanf("%d",
I? 3 1 3 1.1?................................. 3 1.2?............................... 3 1.3!................................... 3 2 4 2.1........................................ 4 2.2.......................................
20 15 14.6 15.3 14.9 15.7 16.0 15.7 13.4 14.5 13.7 14.2 10 10 13 16 19 22 1 70,000 60,000 50,000 40,000 30,000 20,000 10,000 0 2,500 59,862 56,384 2,000 42,662 44,211 40,639 37,323 1,500 33,408 34,472
- 2 -
- 2 - - 3 - (1) (2) (3) (1) - 4 - ~ - 5 - (2) - 6 - (1) (1) - 7 - - 8 - (i) (ii) (iii) (ii) (iii) (ii) 10 - 9 - (3) - 10 - (3) - 11 - - 12 - (1) - 13 - - 14 - (2) - 15 - - 16 - (3) - 17 - - 18 - (4) -
2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4 4 4 2 5 5 2 4 4 4 0 3 3 0 9 10 10 9 1 1
1 1979 6 24 3 4 4 4 4 3 4 4 2 3 4 4 6 0 0 6 2 4 4 4 3 0 0 3 3 3 4 3 2 4 3? 4 3 4 3 4 4 4 4 3 3 4 4 4 4 2 1 1 2 15 4 4 15 0 1 2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4
1 (1) (2)
1 2 (1) (2) (3) 3-78 - 1 (1) (2) - 79 - i) ii) iii) (3) (4) (5) (6) - 80 - (7) (8) (9) (10) 2 (1) (2) (3) (4) i) - 81 - ii) (a) (b) 3 (1) (2) - 82 - - 83 - - 84 - - 85 - - 86 - (1) (2) (3) (4) (5) (6)
r07.dvi
19 7 ( ) 2019.4.20 1 1.1 (data structure ( (dynamic data structure 1 malloc C free C (garbage collection GC C GC(conservative GC 2 1.2 data next p 3 5 7 9 p 3 5 7 9 p 3 5 7 9 1 1: (single linked list 1
ohp07.dvi
19 7 ( ) 2019.4.20 1 (data structure) ( ) (dynamic data structure) 1 malloc C free 1 (static data structure) 2 (2) C (garbage collection GC) C GC(conservative GC) 2 2 conservative GC 3 data next p 3 5
1 C STL(1) C C C libc C C C++ STL(Standard Template Library ) libc libc C++ C STL libc STL iostream Algorithm libc STL string vector l
C/C++ 2007 6 18 1 C STL(1) 2 1.1............................................... 2 1.2 stdio................................................ 3 1.3.......................................... 10 2 11 2.1 sizeof......................................
Microsoft Word - no206.docx
3.2 双方向リスト 今までのリストは 前から順にたどることしかできませんでした 今度は逆にもたどることができる 双方向リストを扱います この場合は 構造体には次を表すポインタの他に前を表すポインタを持つ ことになります 今回は最初と最後をポインタを使うと取り扱いが面倒になるので 最初 (start) と最後 (end) を どちらとも構造体 ( 値は意味を持たない ) を使うことにします こうすることによって
XMPによる並列化実装2
2 3 C Fortran Exercise 1 Exercise 2 Serial init.c init.f90 XMP xmp_init.c xmp_init.f90 Serial laplace.c laplace.f90 XMP xmp_laplace.c xmp_laplace.f90 #include int a[10]; program init integer
untitled
II 4 Yacc Lex 2005 : 0 1 Yacc 20 Lex 1 20 traverse 1 %% 2 [0-9]+ { yylval.val = atoi((char*)yytext); return NUM; 3 "+" { return + ; 4 "*" { return * ; 5 "-" { return - ; 6 "/" { return / ; 7 [ \t] { /*
* n x 11,, x 1n N(µ 1, σ 2 ) x 21,, x 2n N(µ 2, σ 2 ) H 0 µ 1 = µ 2 (= µ ) H 1 µ 1 µ 2 H 0, H 1 *2 σ 2 σ 2 0, σ 2 1 *1 *2 H 0 H
1 1 1.1 *1 1. 1.3.1 n x 11,, x 1n Nµ 1, σ x 1,, x n Nµ, σ H 0 µ 1 = µ = µ H 1 µ 1 µ H 0, H 1 * σ σ 0, σ 1 *1 * H 0 H 0, H 1 H 1 1 H 0 µ, σ 0 H 1 µ 1, µ, σ 1 L 0 µ, σ x L 1 µ 1, µ, σ x x H 0 L 0 µ, σ 0
50. (km) A B C C 7 B A 0
49... 5 A B C. (. )?.. A A B C. A 4 0 50. (km) A B C..9 7. 4.5.9. 5. 7.5.0 4..4 7. 5.5 5.0 4. 4.. 8. 7 8.8 9.8. 8 5. 5.7.7 9.4 4. 4.7 0 4. 7. 8.0 4.. 5.8.4.8 8.5. 8 9 5 C 7 B 5 8 7 4 4 A 0 0 0 4 5 7 8
Microsoft PowerPoint - 06graph3.ppt [互換モード]
![Microsoft PowerPoint - 06graph3.ppt [互換モード]](/thumbs/100/144239321.jpg "Microsoft PowerPoint - 06graph3.ppt [互換モード]")
I118 グラフとオートマトン理論 Graphs and Automata 担当 : 上原隆平 (Ryuhei UEHARA) uehara@jaist.ac.jp http://www.jaist.ac.jp/~uehara/ 1/20 6.14 グラフにおける探索木 (Search Tree in a Graph) グラフG=(V,E) における探索アルゴリズム : 1. Q:={v { 0 }
untitled
II yacc 005 : 1, 1 1 1 %{ int lineno=0; 3 int wordno=0; 4 int charno=0; 5 6 %} 7 8 %% 9 [ \t]+ { charno+=strlen(yytext); } 10 "\n" { lineno++; charno++; } 11 [^ \t\n]+ { wordno++; charno+=strlen(yytext);}
新版明解Ｃ言語 実践編
2 List - "max.h" a, b max List - max "max.h" #define max(a, b) ((a) > (b)? (a) : (b)) max List -2 List -2 max #include "max.h" int x, y; printf("x"); printf("y"); scanf("%d", &x); scanf("%d", &y); printf("max(x,
A/B (2010/10/08) Ver kurino/2010/soft/soft.html A/B
A/B (2010/10/08) Ver. 1.0 kurino@math.cst.nihon-u.ac.jp http://edu-gw2.math.cst.nihon-u.ac.jp/ kurino/2010/soft/soft.html 2010 10 8 A/B 1 2010 10 8 2 1 1 1.1 OHP.................................... 1 1.2.......................................
provider_020524_2.PDF
1 1 1 2 2 3 (1) 3 (2) 4 (3) 6 7 7 (1) 8 (2) 21 26 27 27 27 28 31 32 32 36 1 1 2 2 (1) 3 3 4 45 (2) 6 7 5 (3) 6 7 8 (1) ii iii iv 8 * 9 10 11 9 12 10 13 14 15 11 16 17 12 13 18 19 20 (2) 14 21 22 23 24
ex01.dvi
,. 0. 0.0. C () /******************************* * $Id: ex_0_0.c,v.2 2006-04-0 3:37:00+09 naito Exp $ * * 0. 0.0 *******************************/ #include int main(int argc, char **argv) double
3.1 stdio.h iostream List.2 using namespace std C printf ( ) %d %f %s %d C++ cout cout List.2 Hello World! cout << float a = 1.2f; int b = 3; cout <<
C++ C C++ 1 C++ C++ C C++ C C++? C C++ C *.c *.cpp C cpp VC C++ 2 C++ C++ C++ [1], C++,,1999 [2],,,2001 [3], ( )( ),,2001 [4] B.W. /D.M.,, C,,1989 C Web [5], http://kumei.ne.jp/c_lang/ 3 Hello World Hello
tuat1.dvi
( 1 ) http://ist.ksc.kwansei.ac.jp/ tutimura/ 2012 6 23 ( 1 ) 1 / 58 C ( 1 ) 2 / 58 2008 9 2002 2005 T E X ptetex3, ptexlive pt E X UTF-8 xdvi-jp 3 ( 1 ) 3 / 58 ( 1 ) 4 / 58 C,... ( 1 ) 5 / 58 6/23( )
Taro-リストⅢ（公開版）.jtd
リスト Ⅲ 0. 目次 2. 基本的な操作 2. 1 リストから要素の削除 2. 2 リストの複写 2. 3 リストの連結 2. 4 問題 問題 1 問題 2-1 - 2. 基本的な操作 2. 1 リストから要素の削除 まず 一般的な処理を書き つぎに 特別な処理を書く 一般的な処理は 処理 1 : リスト中に 削除するデータを見つけ 削除する場合への対応 特別な処理は 処理 2 : 先頭のデータを削除する場合への対応
i ii iii iv v vi vii ( ー ー ) ( ) ( ) ( ) ( ) ー ( ) ( ) ー ー ( ) ( ) ( ) ( ) ( ) 13 202 24122783 3622316 (1) (2) (3) (4) 2483 (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) 11 11 2483 13
2 1 list0415.c forfor #include int i, j; for (i = 1; i c-all.dvi
III(994) (994) from PSL (9947) & (9922) c (99,992,994,996) () () 2 3 4 (2) 2 Euler 22 23 Euler 24 (3) 3 32 33 34 35 Poisson (4) 4 (5) 5 52 ( ) 2 Turbo 2 d 2 y=dx 2 = y y = a sin x + b cos x x = y = Fortran
解きながら学ぶC++入門編
!... 38!=... 35 "... 112 " "... 311 " "... 4, 264 #... 371 #define... 126, 371 #endif... 369 #if... 369 #ifndef... 369 #include... 3, 311 #undef... 371 %... 17, 18 %=... 85 &... 222 &... 203 &&... 40 &=...
オートマトンと言語理論 テキスト 成蹊大学理工学部情報科学科 山本真基 ii iii 1 1 1.1.................................. 1 1.2................................ 5 1.3............................. 5 2 7 2.1..................................
r03.dvi
19 ( ) 019.4.0 CS 1 (comand line arguments) Unix./a.out aa bbb ccc ( ) C main void... argc argv argc ( ) argv (C char ) ( 1) argc 4 argv NULL. / a. o u t \0 a a \0 b b b \0 c c c \0 1: // argdemo1.c ---
平成 31 年度 筑波大学大学院博士課程システム情報工学研究科コンピュータサイエンス専攻 博士前期課程 ( 一般入学試験 2 月期 ) 試験問題基礎科目 ( 数学, 情報基礎 ) Mathematics/Fundamentals of Computer Science [ 注意事項 ][Instru
![平成 31 年度 筑波大学大学院博士課程システム情報工学研究科コンピュータサイエンス専攻 博士前期課程 ( 一般入学試験 2 月期 ) 試験問題基礎科目 ( 数学, 情報基礎 ) Mathematics/Fundamentals of Computer Science [ 注意事項 ][Instru](/thumbs/103/158251332.jpg "平成 31 年度 筑波大学大学院博士課程システム情報工学研究科コンピュータサイエンス専攻 博士前期課程 ( 一般入学試験 2 月期 ) 試験問題基礎科目 ( 数学, 情報基礎 ) Mathematics/Fundamentals of Computer Science [ 注意事項 ][Instru")
平成 31 年度 筑波大学大学院博士課程システム情報工学研究科コンピュータサイエンス専攻 博士前期課程 ( 一般入学試験 2 月期 ) 試験問題基礎科目 ( 数学, 情報基礎 ) Mathematics/Fundamentals of Computer Science [ 注意事項 ][Instructions] 1. 試験開始の合図があるまで, 問題の中を見てはいけません. また, 筆記用具を手に持ってはいけません.
I ASCII ( ) NUL 16 DLE SP P p 1 SOH 17 DC1! 1 A Q a q STX 2 18 DC2 " 2 B R b
I 4 003 4 30 1 ASCII ( ) 0 17 0 NUL 16 DLE SP 0 @ P 3 48 64 80 96 11 p 1 SOH 17 DC1! 1 A Q a 33 49 65 81 97 113 q STX 18 DC " B R b 34 50 66 8 98 114 r 3 ETX 19 DC3 # 3 C S c 35 51 67 83 99 115 s 4 EOT
s t 1, 2,..., 10 s t a, b,..., k t s 1, 2,..., 10 1 a, b,..., k 1 s t ts 1 0 ( 2.25) ½ ¾ ½¼ x 1j = 1 x 2c = 1 x 3e = 1
72 2 2 2 2.24 2 s t, 2,..., 0 s t a, b,..., k t s, 2,..., 0 a, b,..., k s t 0 ts 0 ( 2.25) 2.24 2 ½ ¾ ½¼ x j = x 2c = x 3e = x 4s = x 5g = x 6i = x 7d = x 8h = x 9f = x 0k = x ta = x tb = x ts = 9 2.26
178 5 I 1 ( ) ( ) 10 3 13 3 1 8891 8 3023 6317 ( 10 1914 7152 ) 16 5 1 ( ) 6 13 3 13 3 8575 3896 8 1715 779 6 (1) 2 7 4 ( 2 ) 13 11 26 12 21 14 11 21
I 178 II 180 III ( ) 181 IV 183 V 185 VI 186 178 5 I 1 ( ) ( ) 10 3 13 3 1 8891 8 3023 6317 ( 10 1914 7152 ) 16 5 1 ( ) 6 13 3 13 3 8575 3896 8 1715 779 6 (1) 2 7 4 ( 2 ) 13 11 26 12 21 14 11 21 4 10 (
ohp03.dvi
19 3 ( ) 2019.4.20 CS 1 (comand line arguments) Unix./a.out aa bbb ccc ( ) C main void int main(int argc, char *argv[]) {... 2 (2) argc argv argc ( ) argv (C char ) ( 1) argc 4 argv NULL. / a. o u t \0
cpp1.dvi
2017 c 1 C++ (1) C C++, C++, C 11, 12 13 (1) 14 (2) 11 1 n C++ //, [List 11] 1: #include // C 2: 3: int main(void) { 4: std::cout
橡CompSimmAllcpct.PDF
3 1 M dx 1 dx/ 1/ x P 0 (x) x dx x P 0 (x) x+dx P 0 (x+dx) x dx P 0 (x+dx)=p 0 (x)(1-dx/ dx/) x P 0 (x) P 0 (x+dx)=p 0 (x)(1-dx/ dx/) Tayler (dx) P 0 (x)+(dp 0 /dx)dx (dp 0 (x)/dx)dx= -P 0 (x) dx/
連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 準備 問題の定義 αβ 法 16 2 αβ 法の並列化 概要 Young Brothers Wa
連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 準備 16 1.1 問題の定義 16 1.2 αβ 法 16 2 αβ 法の並列化 17 2.1 概要 17 2.2 Young Brothers Wait Concept 17 2.3 段数による逐次化 18 2.4 適応的な待機 18 2. 強制終了
A/B (2018/06/08) Ver kurino/2018/soft/soft.html A/B
A/B (2018/06/08) Ver. 1.0 kurino@math.cst.nihon-u.ac.jp http://edu-gw2.math.cst.nihon-u.ac.jp/ kurino/2018/soft/soft.html 2018 6 8 A/B 1 2018 6 8 2 1 1 1.1 OHP.................................... 1 1.2
PowerPoint Presentation
二分探索木 今回の要点 二分探索木の構造 どのような条件を満たさねばならないか? 二分探索が効率よく出来るため 二分探索木の操作 探索の方法 挿入の方法 削除の方法 各操作の実装コード 二分探索木の性質 どのような形がもっと探索に適しているか? 二分探索木とは 木構造 枝分かれした構造を表現するのに適する 根から葉に向かってたどる = 探索 何らかの特徴を持って構成されていると探索しやすい 二分探索木
/* do-while */ #include <stdio.h> #include <math.h> int main(void) double val1, val2, arith_mean, geo_mean; printf( \n ); do printf( ); scanf( %lf, &v
1 http://www7.bpe.es.osaka-u.ac.jp/~kota/classes/jse.html kota@fbs.osaka-u.ac.jp /* do-while */ #include #include int main(void) double val1, val2, arith_mean, geo_mean; printf( \n );
C¥×¥í¥°¥é¥ß¥ó¥° ÆþÌç
C (3) if else switch AND && OR (NOT)! 1 BMI BMI BMI = 10 4 [kg]) ( [cm]) 2 bmi1.c Input your height[cm]: 173.2 Enter Input your weight[kg]: 60.3 Enter Your BMI is 20.1. 10 4 = 10000.0 1 BMI BMI BMI = 10
Gauss
15 1 LU LDL T 6 : 1g00p013-5 1 6 1.1....................................... 7 1.2.................................. 8 1.3.................................. 8 2 Gauss 9 2.1.....................................
1.ppt
/* * Program name: hello.c */ #include int main() { printf( hello, world\n ); return 0; /* * Program name: Hello.java */ import java.io.*; class Hello { public static void main(string[] arg)
1 1.1 C 2 1 double a[ ][ ]; 1 3x x3 ( ) malloc() 2 double *a[ ]; double 1 malloc() dou
![1 1.1 C 2 1 double a[ ][ ]; 1 3x x3 ( ) malloc() 2 double *a[ ]; double 1 malloc() dou](/thumbs/98/138757599.jpg "1 1.1 C 2 1 double a[ ][ ]; 1 3x x3 ( ) malloc() 2 double *a[ ]; double 1 malloc() dou")
1 1.1 C 2 1 double a[ ][ ]; 1 3x3 0 1 3x3 ( ) 0.240 0.143 0.339 0.191 0.341 0.477 0.412 0.003 0.921 1.2 malloc() 2 double *a[ ]; double 1 malloc() double 1 malloc() free() 3 #include #include
ip-leda-homepage.dvi
LEDA:,,,, Kurt Mehlhorn LEDA LEDA 1 [2] LEDA Library for Efficient Data types and Algorithms LEDA LEDA C++ 1 LEDA LEDA Dijkstra( ) LEDA 2 : LEDA LEDA VORONOI() 1, LEDA voronoi demo.c LEDA 2 1: LEDA LEDA
II ( ) prog8-1.c s1542h017%./prog8-1 1 => 35 Hiroshi 2 => 23 Koji 3 => 67 Satoshi 4 => 87 Junko 5 => 64 Ichiro 6 => 89 Mari 7 => 73 D
II 8 2003 11 12 1 6 ( ) prog8-1.c s1542h017%./prog8-1 1 => 35 Hiroshi 2 => 23 Koji 3 => 67 Satoshi 4 => 87 Junko 5 => 64 Ichiro 6 => 89 Mari 7 => 73 Daisuke 8 =>. 73 Daisuke 35 Hiroshi 64 Ichiro 87 Junko
joho09.ppt
s M B e E s: (+ or -) M: B: (=2) e: E: ax 2 + bx + c = 0 y = ax 2 + bx + c x a, b y +/- [a, b] a, b y (a+b) / 2 1-2 1-3 x 1 A a, b y 1. 2. a, b 3. for Loop (b-a)/ 4. y=a*x*x + b*x + c 5. y==0.0 y (y2)
II 3 yacc (2) 2005 : Yacc 0 ~nakai/ipp2 1 C main main 1 NULL NULL for 2 (a) Yacc 2 (b) 2 3 y
II 3 yacc (2) 2005 : Yacc 0 ~nakai/ipp2 1 C 1 6 9 1 main main 1 NULL NULL 1 15 23 25 48 26 30 32 36 38 43 45 47 50 52 for 2 (a) 2 2 1 Yacc 2 (b) 2 3 yytext tmp2 ("") tmp2->next->word tmp2 yytext tmp2->next->word
1.3 ( ) ( ) C
1 1.1 (Data Base) (Container) C++ Java 1.2 1 1.3 ( ) ( ) 1. 2. 3. C++ 2 2.1 2.2 2.3 2 C Fortran C++ Java 3 3.1 (Vector) 1. 2. ( ) 3.2 3 3.3 C++ C++ STL C++ (Template) vector vector< > ; int arrayint vector
第5回お試しアカウント付き並列プログラミング講習会
qstat -l ID (qstat -f) qscript ID BATCH REQUEST: 253443.batch1 Name: test.sh Owner: uid=32637, gid=30123 Priority: 63 State: 1(RUNNING) Created at: Tue Jun 30 05:36:24 2009 Started at: Tue Jun 30 05:36:27
[1] #include<stdio.h> main() { printf("hello, world."); return 0; } (G1) int long int float ± ±
![[1] #include<stdio.h> main() { printf(hello, world.); return 0; } (G1) int long int float ± ±](/thumbs/99/143405735.jpg "[1] #include<stdio.h> main() { printf(hello, world.); return 0; } (G1) int long int float ± ±")
[1] #include printf("hello, world."); (G1) int -32768 32767 long int -2147483648 2147483647 float ±3.4 10 38 ±3.4 10 38 double ±1.7 10 308 ±1.7 10 308 char [2] #include int a, b, c, d,
a n a n ( ) (1) a m a n = a m+n (2) (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 552
3 3.0 a n a n ( ) () a m a n = a m+n () (a m ) n = a mn (3) (ab) n = a n b n (4) a m a n = a m n ( m > n ) m n 4 ( ) 55 3. (n ) a n n a n a n 3 4 = 8 8 3 ( 3) 4 = 8 3 8 ( ) ( ) 3 = 8 8 ( ) 3 n n 4 n n
P06.ppt
p.130 p.198 p.208 2 1 double weight[num]; double min, max; min = max = weight[0]; for( i= 1; i < NUM; i++ ) if ( weight[i] > max ) max = weight[i]: if ( weight[i] < min ) min = weight[i]: weight 3 maxof(a,
1 return main() { main main C 1 戻り値の型 関数名 引数 関数ブロックをあらわす中括弧 main() 関数の定義 int main(void){ printf("hello World!!\n"); return 0; 戻り値 1: main() 2.2 C main
C 2007 5 29 C 1 11 2 2.1 main() 1 FORTRAN C main() main main() main() 1 return 1 1 return main() { main main C 1 戻り値の型 関数名 引数 関数ブロックをあらわす中括弧 main() 関数の定義 int main(void){ printf("hello World!!\n"); return
() () (parse tree) ( (( ) * 50) ) ( ( NUM 10 + NUM 30 ) * NUM 50 ) ( * ) ( + ) NUM 50 NUM NUM (abstract syntax tree, AST) ( (( ) * 5
3 lex yacc http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/ 2018 6 1 () () (parse tree) ( ((10 + 30) * 50) ) ( ( NUM 10 + NUM 30 ) * NUM 50 ) ( * ) ( + ) NUM 50 NUM NUM 10 30 (abstract syntax tree,