おしらせ
この科目を履修し単位を取得する予定の方は, 講義初回に必ずご出席ください.
全ての課題は kibaco から提出してください. 提出期限は原則として当日の 23:59 です.
課題
自己紹介をお願いします.
興味深く拝見しました (^^)いま興味のある数学・数理科学(の分野)について自由に答えてください. これまで学んだ内容でも, これから勉強したい内容でも何でも構いません.
興味深く拝見しました (^^)自分の氏名が表示されるプログラムを書いてコンパイル(実行)しなさい. 入力プログラムだけでよい(出力結果などは載せなくてよい).
スライドの printf の例文を名前に変えるだけで OK.文章「1.23+4.56は5.79です」を表示するプログラムを, 書式指定を用いて作成しなさい.
printf("%.2f+%.2fは%.2fです",1.23,4.56,1.23+4.56);
他にもいろいろ書き方がある.123 を 00000123 と出力するための書式指定を答えなさい.
printf("%08d",123);
他にもいろいろ書き方がある.C言語では割り算をスラッシュ / で行う. このとき 3/2 を書式指定 %f で出力すると 0.000000 や 1 という誤った答えが返される. これを正しい答え(例えば 3/2 や 1.500000 など)を出力するように修正しなさい. なお書籍や web 等の記事を参照した場合は, その文献を明記すること.
書式指定を %d/%d にして分子・分母を入力してもよいし, 例えば分子を小数にして %f に 3/2.0 を対応させればよい. 同様の処理に型キャストがある(後日解説する).
課題 問題 1-4 は全員解答すること. 余裕がある人は問題 5,6 にも解答せよ.
以下のプログラムは正しく出力されない. この原因を特定し, 正しく出力できるよう修正しなさい.
#include <stdio.h>
#include <string.h>
int main(){
char s[20] = "My name is Shun'ichi Yokoyama";
printf("%s\n",s);
strcpy(s,"and my favorite is watching movie");
printf("%s\n",s);
}
配列 s の容量が20しかないため, 文字溢れが発生しているのが原因. この数値を例えば 40 などに増やしておけば OK.整数型 unsigned long long int で扱える最大の整数を答えなさい. ただし int 型で扱える整数は −2147483648 から 2147483647 とし, 2147483648=2^31 である. 答えの根拠も簡単に述べること(詳細な計算過程は必要なく, べき乗も計算しなくてよい).
unsigned int がサイズ 2^32 なので, 2倍処理を2回行えば long long となりサイズは 2^128. 値は0から始まるので, 扱える最大値は 2^128-1 が正解. ちなみに書き下すと 340282366920938463463374607431768211455.以下のプログラムにおいて, 最後の printf で出力される a の値とその変化の過程について述べなさい. 変数が int 型であることに注意せよ.
int a,b,c; a=5; b=7; c=2;
a -= b/c;
c += b-a%c;
a = (c-b)*a;
printf("%d",a);
最後の a は 4 が出力される. 2行目で a=5-(7/2)=5-3=2 となり(7/2 が切り捨て処理であることに注意せよ), 3行目で c=2+7-(2%2)=9 となるから, 4行目は a=(9-7)*2=4 となる.以下のプログラムを考える:
short a,b,c; a=12345, b=23456;
c=a+b;
printf("%d+%d=%d",a,b,c);
これを実行すると 12345+23456=-29735 という誤った等式が出力される. これを正しい答えを出力するように修正しなさい.
short 型は 32767 までしかサポートできないため型溢れが起こっていることが原因. 例えば int 型にするか unsigned short 型にすればよい.世界で用いられている気温の単位として, 摂氏(degree Celsius, ℃)と華氏(degree Fahrenheit, ℉)が知られている. それぞれの定義を調べ, どちらか一方の数値が与えられたときにもう一方の数値に変換するプログラムを作成しなさい. 変換の向きはどちらでもよいし, 両方作成してもよい. 変数は float を用いよ(書式指定は自由に決めてよい).
例えば「華氏 = 1.8*摂氏 + 32」という公式を使うのならば F=1.8*C+32 とし, F,C を float 型で扱えば OK.問題4のように, short 型や int 型の場合は誤計算(オーバーフロー)を引き起こさないよう注意をはらう必要がある. それならば, 最初から float や double で全ての演算を行えばよいはずであるが, 実際のプログラムでは必ずしもそのようになっていない. その理由を自由に考察してみよ.
float や double 型は short や int 型に比べて巨大な数の範囲を扱えるが, その分事前に確保しておくべきメモリ領域(記憶媒体にかける負荷)も大きく, 計算によっては無駄なデータ領域を使うことになり非効率である. とくに小型デバイスにおける実装では, 搭載できる記憶媒体のデータサイズも大きいとはいえないため, 一律に float や double を適用するのは適切ではない.
課題
巣穴から直線距離で D センチメートル離れたところに1匹のカエルがおり, 巣穴にまっすぐ帰ろうとしている. カエルは次の2つのジャンプができる:
(a) 大ジャンプ(1回につき L センチメートル進む)
(b) 小ジャンプ(1回につき 1 センチメートル進む)
このとき, 与えられた D, L に対して, カエルが巣穴に帰るための最小ジャンプ回数を求めるプログラムを作成しなさい. ただし D, L は int(または unsigned int)型とし, あらかじめ適当な値を指定しておいてよい.
まず残り距離が L 未満になるまで大ジャンプをすればよく, その回数は D/L である(切り捨て処理だからちょうど回数が得られる). また余り D%L が小ジャンプで進むべき距離であり, 1回につき1だからその回数も D%L に一致する. 従って求める(出力すべき)回数は D/L+D%L であり, これを出力すれば OK.
Additional Q: 巣穴をいったん超えたほうが回数が少なくなることもある. これは D mod L の値と [L/2] の値を比較して, 前者が小さければ小ジャンプに切り替え, 大きければ1度大ジャンプで飛び越えてから小ジャンプで逆戻りすればよい. ただし [L/2] は L/2 以上の最小の自然数.自然数 N が与えられたとき, N が5で割り切れるかどうかを判定するプログラムを作成しなさい. ただし自然数 N はあらかじめ指定してよく, 出力などの体裁は自由に決めてよい.
例: N=25 ならば出力は yes, N=26 ならば出力は no.
N%5(Nを5で割った余り)が0ならば yes, それ以外は no として if/else で分岐させればよい.自然数 N が与えられたとき, N が5で 何回 割り切れるかを求めるプログラムを作成しなさい. ただし自然数 N はあらかじめ指定してよく, 出力などの体裁は自由に決めてよい.
例: N=25 ならば出力は2, N=26 ならば出力は0, N=250 ならば出力は3.
やり方はいくつかあるが, 例えば初期値を int i=0 とし, while(N%5==0) で N/=5; i++; を実行して i を print する. これはNが5の倍数である限り N/5 をNに上書きし, その度に回数 i を更新するプログラムである. N を出力として使いたければ, while ループの前に n=N; などとして別の変数に格納しておけば OK.
第4回 (4/30) これまでの復習(演習1)
課題 問題 1-3 は全員解答すること. 余裕がある人は問題 4 にも解答せよ.
1から100までの和を計算するプログラムを以下に示す:
int x,i;
for(i=1;i<=100;i++){
x=x+i;
}
printf("%d\n",x);
このプログラムは正しくない. その理由を簡潔に述べ, 正しいプログラムに修正しなさい.
変数の初期化を行っていないため, 環境によっては間違った出力を与えることがある. 例えば宣言部で
int x=0;
などとしておけばよい.ある建設会社は, 新しい超高層オフィスビルの建設依頼を受けている. 依頼主からは次が要求されている:
(a) オフィスビルの高さは300メートルであること.
(b) すべての階が同じ高さであること.
(c) 1階あたりの高さは2メートル以上とし, 自然数であること(2.5メートルなどにはしない).
(d) 高さの上限 U はまだ未定のため, あとで決められるようにしておくこと.
(e) U を決めたとき, 何通りの建て方ができるかを計算できるようにしてほしいこと.
例えば U=4 のとき, ビルの建て方 (e) は「1階あたり2メートルの150階建」or「1階あたり3メートルの100階建」or「1階あたり4メートルの75階建」の3通りとなる(もちろん床や天井の厚みは無視している).
このとき, 与えられた U に対して (e) を求めるプログラムを作成しなさい. U はあらかじめ適当な値を指定してよいが, int 型を用いること.
初期値を v=0 とし, for(i=2; i<=U; i++) を実行する. 内部では 300%i==0 のときのみ v++; を実行する if 文を入れておき, for ループ終了時点での v の値が (e) の答えとなる. if 文が true である場合「1階あたり i メートルの 300%i 階建て」と print すれば情報も出力できる.if 文, for 文, while 文を すべて 含むような自作プログラムを1つ作成しなさい.
自由解答. よく書けているものが多かったです.型の定義を重視するC言語において, signed 型と unsigned 型を同一のプログラムで扱うことは極めて危険である. それはなぜか, 具体例を挙げて説明しなさい.
例えばマイナスの値は signed 型では扱えるが unsigned 型では範囲外となり, 予期せぬエラーが生じる可能性がある. 例えば
short a;
unsigned short b;
a=11; b=-10;
printf("%d",a+b);
を実行すると 65537 となり, short 型の範囲からも逸脱する. ただし 65537 という数字は paiza が補完処理をしている(つまり -10 を 65526 に置き換えている)ため, ある意味では全くの間違いとはいえない.
課題 問題 1,2 は全員解答すること. 余裕がある人は問題 3 にも解答せよ.
AさんとBさんの2人が遊園地のボール入れ対決をしている. ボールを投げて穴に入れば, 以下のルールで得点がつく:
○ 大きい穴に入れば1点, 20個入る毎にボーナス10点追加.
○ 小さい穴に入れば3点, 10個入る毎にボーナス15点追加.
AさんとBさんが穴に入れたボールの数(大小合わせて4つの引数)に対して, どちらが勝ちか, または引き分けであるかを判定するプログラムを, 関数を用いて作成しなさい.
例えば小さい穴に入ったボールの数を n とすれば, 得点は 3*n+15*(n/20) である(割り算は切り捨て演算であるから商が得られている). あとは関数の形で総得点を計算し if 文で分岐させれば OK.自然数 N が入力されたとき, フィボナッチ数列の第 N 項を表示するプログラムを 再帰 関数を用いて作成しなさい. なお便宜的に, 第0項を0, 第1項と第2項を1と定義し, 以下 2,3,5,8,13,... と続くものとする.
例えば以下の通り:
int fibonacci(int n){
if(n==0)
return 0;
else if(n==1)
return 1;
else
return fibonacci(n-2)+fibonacci(n-1);
}自然数 N が入力されたとき, N 以下の「双子素数」をすべて表示するプログラムを関数を用いて作成しなさい. ただし双子素数とは p, p+2 が共に素数となるようなペアのことである. 例えば (3,5), (5,7), (11,13) などであり, このようなペアが無限個あるかどうかは未解決問題である(双子素数予想). なお上限は「p が N 以下」でも「p+2 が N 以下」でもどちらでも構わない(プログラムを組みやすい方にしてよい).
補足:双子素数予想についてはこの10年で飛躍的な進展があり p, p+246 が共に素数であるようなペアが無限個あることが2014年に証明された(J. メイナードはこの結果を含む研究により2022年にフィールズ賞を受賞した. なお最初のブレークスルーは 246 の値が7000万程度のオーダーであり, これを2まで縮めるための研究が進んでいる). また関連する予想としてグリーン・タオの定理があり, この一般化にあたる「数体の素元星座定理」が2021年にプレプリントとして発表されたが, この結果は日本人数学者によるものである. 2023年, 著者の1人である 関真一朗氏(青山学院大学・助教)が書籍 グリーン・タオの定理 を発表. 関氏は 素数大富豪 とよばれるカードゲームの発案者でもある.
素数判定プログラム isprime が得られれば isprime(n) と isprime(n+2) が共に true(以下では1)を返せば OK とすればよい. 素数判定プログラムは数多くの組み方があるが, 例えば Eratosthenes の篩アルゴリズムならば以下のように書ける:
int isprime(int n){
int i;
if(n<=3)
return 1;
for(i=2;i<=(n/2);i++){
if((n%i)==0)
return 0;
}
return 1;
}
なお i の上限を上では n/2 としているが, n の平方根(の ceiling)まで改良できる.
課題 問題 1,2 は全員解答すること. 余裕がある人は問題 3 にも解答せよ.
ある学生5人の定期試験の成績がそれぞれ 54点, 49点, 97点, 65点, 89点であったとする. この5人の成績をこの順番で格納した配列 scr[ ] を作成しなさい. その後, 5人の成績を高い得点順にソートした配列を プログラムを組むことで scr[ ] に上書き作成しなさい. つまり手入力(人力でソート)は禁止という意味である. 正常に完了すれば scr[0] には 97, scr[1] には 89 という風に格納されるはずである.
ヒント: 前に学習した比較演算子と条件分岐を思い出そう. なおソートの手法は1通りではない(後期「アルゴリズムB&演習」で詳しく学ぶ). ここでは単純に swap(前回やった temp を挟む手法)でやるとよい.
例えば2重 for 文で処理すればよい:
int str[]={54,49,97,65,89};
int i,j,tmp;
for(i=0;i<5;i++){
for(j=i+1;j<5;j++){
if(scr[i]<scr[j]){
tmp=scr[i];
scr[i]=scr[j];
scr[j]=tmp;
}
}
}これまでの講義・演習で登場したプログラムを1つ選び, 同じものを C言語以外の プログラミング言語を用いて作成しなさい. 実装にあたっては, 標準ライブラリはもとより, あらゆる拡張機能を必要に応じて用いて構わない. また講義では Python, Java, JavaScript, Haskell, Julia を紹介したが, もちろんそれ以外の言語でも構わない. また当該プログラムを自力で組むのが難しい場合は, 何か新しくプログラムを考え, C言語で実装すること.
バリエーション豊富なプログラムで大変興味深かったです. Python と JavaScript で組んだ人が比較的多い印象でした.以下のような出力を与えるプログラムを作成しなさい.
x
xx
xxx
xxxx
xxxxx
xxxx
xxx
xx
x
要求事項: 再帰呼び出しを必ず用いること.
禁止事項: printf 関数を用いて単に表示させてはいけない(もちろん printf 関数は使う:つまり上記ではxが5つ並んだ後折り返しているが, プログラムの数値を変更すれば任意の桁数に変更できるようなプログラムにすること).
ヒント: printf 関数では改行命令 \n がなければ改行されない. このことをうまく活用せよ.
なお, プログラムを完成させるのが難しい場合は「このような流れのプログラムを書ければ実行できるはず」という意図が伝わる文章で解答してもよい. これはいわゆる「レシピエント」「フローチャート」とよばれるものであり, 実際の開発現場でも作成が求められる.
例えば以下のような関数 five を作ればよい. x は char 型であり, 入力によって数を変更できるようになっている.
void five(int n, int max, char digit){
int i;
for(i=0;i<n;i++){
printf("%c",digit);
}
printf("\n");
if(n<max){
five(n+1,max,digit);
}
for(i=1;i<n;i++){
printf("%c",digit);
}
printf("\n");
}
int main(void){
five(1,5,'x');
}
第7回 (5/21) これまでの復習(演習2)
課題 ※ 前回(第6回, 5/14)の問題3についても解答可能
第4回(4/30)の問題1と同じ実行結果を与えるプログラムを 再帰呼び出しを用いて 作成しなさい.
例えば以下のような再帰関数 add を作ればよい.
int add(int n){
if(n==0){
return 0;
}else{
return(add(n-1)+n))
}
}多次元配列を用いて「掛け算九九」を表示するプログラムを作成しなさい. 例えば
a[5][4];
20
のように格納された多次元配列を作成すること.
例えば以下のように書けばよい.
int i=0;
int j=0;
int a[10][10];
for(i=0;i<10;i++){
for(j=0;j<10;j++){
a[i][j]=i*j;
}
}
なお i=0 or j=0 のところはすべて0が格納される(ダミー項).以下のプログラムは正しくない. その理由を簡潔に述べ, 正しいプログラムに修正しなさい.
int i;
int x[5]={-5,2,-3,-4,1};
unsigned int bdr=0;
for(i=0;i<5;i++){
if(x[i]>=bdr){
printf("%dは正の値です\n",x[i]);
}else{
printf("%dは負の値です\n",x[i]);
}
}
型 int と unsigned int が混在しているために, 整数の引き渡し処理を間違えたことが原因. 例えば
if(x[i]>=(int)bdr)
などとすればよい.プログラミング言語のうち Haskell(や paiza.IO で使える Clojure, Erlang, F#)などは「関数型プログラミング言語」とよばれる. これらは C や Python などの「手続き型プログラミング言語」とは設計思想が異なる. その違いについて調査し, 関数型言語を採用することのメリット・デメリットについて自由に考察しなさい.
メリットのひとつは講義でも述べた通り, 人間にとって直感的かつ自然にプログラムが組める点である. またオブジェクト同士の対応がはっきりしているため, 長いプログラムであっても整序関係が読み取りやすい. しかしその一方で, それぞれのプログラムがバックエンドでどのように動いているか(機械語にどのように変換され, コンパイラが命令を与えているか)を把握しづらいため, C言語のようにチューニングすることが困難である. 高速・効率計算を目指す人にとってはデメリットになりうる.
※ 提出期限を 6/2(日)に延長しました
課題 以下はすべて Magma Calculator を用いて計算せよ. ソースコードと実行結果の両方をコピー&ペーストして提出すること.
30桁以上の自然数を1つ選び, 素因数分解を行いなさい.
Factorization(ここに自然数を入力);自然数の積 402×409×416×・・・×493×500 を計算するプログラムを書き, 実行しなさい. ただし, 計算式をすべてベタ打ちで記述してはいけない(Magma 搭載の関数を用いて計算せよという意味).
例えば &*[7*n+3: n in[57..71]]; や &*[402+7*n: n in [0..14]]; のように初項・末項を直接指定してもよいし, 現れる自然数が7で割ると3余ることを用いて &*[n: n in [402..500] | n mod 7 eq 3]; のように書くこともできる(後半で条件をつけている). 何れにせよ答えは 6279739080859050124454951342776934400000 である.不定方程式 x+26*y^2+91*z^4=894964220 をみたすような自然数 (x,y,z) の組を1つ見つけなさい. ただし x^n はxのn乗(べき乗)を表す.
exists(x,y,z){<x,y,z> : x,y,z in [1..100] | x+26*y^2+91*z^4 eq 894964220}; x; y; z; を実行すればよい. x, y, z の範囲を適切に広げるところがポイント. 答えは例えば x=98, y=31, z=56 となる.自作の関数を1つ作成しなさい. ただしデモンストレーションで扱った例とは異なるものとし, 何を計算するための関数なのかを明記すること.
自由解答. よくできていました.
課題 ※ 提出期限は 6/7(金)です. あわてず, 焦らずゆっくり取り組んでみてください.
以下のコードにプログラムを書き足し, 2024 を表示するプログラムとしなさい. ただし x に直接 2024 を代入してはならない(つまりポインタ変数 p を必ず利用せよ).
int x;
int* p;
printf("%d",x);int 型数列 a[ ]={1,2,3,4,5,6,7,8,9,10} の各要素を逆順に表示させるプログラムを ポインタを用いて 作成しなさい. ただし配列の要素を インデックスを用いて取り出してはならない(a[0], a[1] のような表記を使ってはいけないという意味である).
文字列 s[ ]="aLGOritHmA" を考える. このとき, 文字列 aLGOritHmA を全て大文字列 ALGORITHMA に変換するプログラムを ポインタを用いて 作成しなさい.
ヒント1: 関数 toupper は, 小文字1字を大文字に変換する関数である. この関数を使うには, ヘッダファイル ctype.h を事前に読み込む必要がある. 例えば toupper(’a’) は A を返す. 最初から大文字の場合は変化しない.
ヒント2: ポインタ char* p を使って配列 s の要素を順に処理する方法は, 例えば以下の通り:
p=s;
while(*p!=’\0’){
*p=<行いたい処理>;
p++;
}
ここで p は配列の先頭項 s[0] へのポインタとみなせる. 文字列の最後の要素は null 文字だから, そこに到達するまで while 文で動かし, ポインタそのものにインクリメント演算子をつければよい.
細かい補足: 直接 s をポインタとみなせばよいと思うかもしれないが, この場合は s を null 文字を含む要素11の配列としてあらかじめ定義しておかなければならない(これがないと while 文 で配列サイズエラーが起きる). 別のポインタ p から s を読みにいけば s の要素サイズに関係なく null 文字を補って while 文を実行できる. null 文字が不要であった int 型(課題2)との違いに注意しておこう.
第10回 (6/11) ポインタを理解する Part 2:メモリ領域の確保とポインタ・構造体・型の再定義 スライド
課題
第11回 (6/18) ポインタの応用(演習3)
課題
第12回 (6/25) これまでの復習(演習4)
課題
第13回 (7/2) 時刻取得関数・乱数 rand, srand スライド
課題
第14回 (7/9) 特別回:ハードウェアを知ろう / 最終レポート課題について
今回は課題はありません. なお当日のスライド・配布資料は権利関係のため公開できませんので, オンサイト(対面)でのみ提供いたします. また最終レポート課題は第15回(7/16)の欄に掲載します.
第15回 (7/16) 総まとめ / 最終レポート課題作成
課題
Contact: s-yokoyama [at] tmu.ac.jp