Ｃアルゴリズム 組み合わせ(再帰)

数学的な説明はしませんが組み合わせは漸近式で求めることができます漸近式は単純な計算を繰り返すため再帰を作る問題でよく使われます。

#include＜stdio.h＞

main(){
　　　　long combi(int ,int);
　　　　int n,r;

　　　　printf("Input nCr n,r : ");
　　　　scanf("%d %d",&n,&r);
　　　　printf("%dC%d = %d",n,r,combi(n,r));
}

long combi(int n, int r){
　　　　if(r == 0 || r == n) return 1;
　　　　else return (n - r + 1) / r * combi(n,r-1);
}

Ｃアルゴリズム ユークリッドの互除法(再帰)

再帰プログラムの中では総和(Sum),階乗,ハノイの塔に続く最初に覚えるアルゴリズムのひとつです。再帰プログラムは繰り返し、条件分岐の次に覚えるプログラムで主に単純作業の繰り返しに利用されます。頭の中では理解しづらいので実際にトレースし紙に書き起こすなどしてプログラムの動きを理解していくとよいでしょう。

#include＜stdio.h＞

main(){
　　　　int x,y;
　　　　int gcd(int, int);　　/*ユークリッドの互除法の計算*/

　　　　printf("input x y : ");
　　　　scanf("%d %d", &x, &y);
　　　　printf("%d",gcd(x,y));
}

int gcd(int x, int y){
　　　　if(y == 0) return x;　　　/*終了条件*/
　　　　else　　 return gcd(y, x % y);　/*ユークリッドの互除法*/
}

Ｃアルゴリズム エラトステネスの篩

学校の課題の関係上出力等を提出用にいじっています。前回のビット回転同様にプログラムには無駄が多くわかりづらい考え方をしているかもしれませんが参考にどうぞ。一応わかるようにコメント、インデントをつけていますがわかりづらいかもしれません。

#include ＜stdio.h＞

#define N 100000
#define tn 1471821271

main()
{
　　　　int i,j,ans = 0,n = 0,nc = 0;
　　　　//n:出力数をカウント nc:素数のカウント ans:素因数分解の要素数
　　　　int sosur[N] = {0,0};
　　　　//2～100,000の数を記憶 配列0,1番目は初期値を0とする
　　　　int sosuw[N]; //素数を出力する配列
　　　　int bun[100]; 　　　　//素因数分解で出た素数を格納
　　　　void sosu(int sosur[N], int sosuw[N], int dn, int *nc);
　　　　//エラトステネスの篩
　　　　void soinsu(int sosuw[N], int bun[100], int sn, int nc, int *b);
　　　　//素因数分解を計算 sn:素因数分解する数

　　　　sosu(sosur, sosuw, N, &nc); //エラトステネスの篩

　　　　//出力処理
　　　　for(j = 1 ; j <= 30; j++){ //出力配列の最初1行10個とし3行出力
　　　　　　　　printf("%6d",sosuw[j-1]);
　　　　　　　　if((j % 10) == 0){ //出力した素数が10個のとき改行
　　　　　　　　　　　　printf("\n");
　　　　　　　　}
　　　　}
　　　　printf("\n");

　　　　n = 1;
　　　　i = nc - (nc / 10) * 10; //素数の総数の1の位を取り出す
　　　　if(i==0){ //1の位が0のとき
　　　　　　　　i = 10;
　　　　}
　　　　for(j = (nc - (20+i)) ; j <nc; j++){//出力配列の最後の3行を出力 　　　　　　　　if(n == 10){ //出力した素数が10個のとき改行
　　　　　　　　　　　　printf("\n");
　　　　　　　　　　　　n = 0;
　　　　　　　　}
　　　　　　　　n += 1; //出力した素数をカウント
　　　　}

　　　　printf("\n");
　　　　printf("count:%d\n\n", nc); //素数の個数を出力

　　　　soinsu(sosuw, bun, tn, nc, &ans); //素因数分解を計算
　　　　printf("素因数分解:1471821271\n");
　　　　if(ans == 0){
　　　　　　　　　printf("素因数分解できませんでした");
　　　　}
　　　　else{
　　　　　　　　　for(i = 0; i <ans; i++){ //素因数分解の結果出力 　　　　　　　　　}
　　　　}

}

void sosu(int sosur[N], int sosuw[N], int dn, int *nc){
//エラトステネスの篩
　　　　int i,j;

　　　　for(i = 2; i <= N; i++){ //2～100,000を配列に格納
　　　　　　　　　sosur[i] = i;
　　　　}

　　　　for(i = 2; (i*i) <= N ; i++){ //エラトステネスの篩
　　　　　　　　　if(sosur[i] != 0){ //配列のi番目が0のとき何もしない
　　　　　　　　　　　　　for(j = 2*i; j <N; j+=i){ 　　　　　　　　　　　　　　　sosur[j] = 0;
　　　　　　　　　　　　　}
　　　　　　　　　}
　　　　}

　　　　for(i = 0; i <N; i++){//配列に格納されている素数を出力配列に入れる 　　　　　　　　　　　　sosuw[*nc] = sosur[i];
　　　　　　　　　　　　*nc += 1; //素数をカウント
　　　　　　　　　}
　　　　}
}

void soinsu(int sosuw[N], int bun[100], int sn, int nc, int *b){
　//素因数分解
　　　　int i = 0,j = 0,w,m; //m:snを割る数(素数)
　　　　int temp; //mで割られた数

　　　　temp = tn;
　　　　while(temp != 1){ //割られて1とならない間繰り返す
　　　　　　　　m = sosuw[i]; //出力配列の素数をmに代入
　　　　　　　　if((temp % m) == 0){ //割り切れたとき
　　　　　　　　　　　　temp = temp / m;
　　　　　　　　　　　　bun[j] = m; //素因数分解の要素を格納
　　　　　　　　　　　　j += 1;
　　　　　　　　　　　　i = 0;
　　　　　　　　}
　　　　　　　　if(nc == i){
　　　　　　　　　　　　j = 0;
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　i += 1;
　　　　}
}

Ｃアルゴリズム ビット回転

入力された１６進数を２進数に変換しシフト量分回転させるプログラムです。
コメントやインデントの関係上読みにくいかもしれませんが参考にどうぞ
includeの＜＞←はブログで表示されてなかったようなので大文字にしましたコンパイルをするときは小文字に直してください。

#include ＜stdio.h＞
#include ＜string.h＞
#define N 32
static unsigned int f[32] =
{ 0x00000001, 0x00000002, 0x00000004, 0x00000008,
0x00000010, 0x00000020, 0x00000040, 0x00000080,
0x00000100, 0x00000200, 0x00000400, 0x00000800,
0x00001000, 0x00002000, 0x00004000, 0x00008000,
0x00010000, 0x00020000, 0x00040000, 0x00080000,
0x00100000, 0x00200000, 0x00400000, 0x00800000,
0x01000000, 0x02000000, 0x04000000, 0x08000000,
0x10000000, 0x20000000, 0x40000000, 0x80000000 };

main(){
unsigned int e,er,el;
//e:入力した16進数 er:右にシフトした16進数 el:左にシフトした16進数
unsigned int s; //s:シフトする量
void prbit(unsigned int ); //16進数を2進数のビット列に変換出力
void lshift( unsigned int s, unsigned int e, unsigned int *el);
　　　　//左シフト回転
void rshift( unsigned int s, unsigned int e, unsigned int *er);
//右シフト回転

printf("16進数を入力せよn");
scanf("%x",&e); //16進数の入力

printf("ビット表示 ");
prbit(e); //ビット列に変換出力

printf("nビットシフト量を入力せよn");
scanf("%d",&s); //シフト量の変換

lshift(s,e,&el); //左シフト回転
printf("%d-ビット左回転",s);
prbit(el); //回転したビット列を出力

rshift(s,e,&er); //右シフト回転
printf("n%d-ビット右回転",s);
prbit(er); //回転したビット列の出力

}

void prbit(unsigned int e){ //ビット出力
int i,bit;

for(i = 0; i <N; i++){ 　　　　　　　　//入力データとiビットのみが1のデータとのビット積
bit = 1;　　//1ならば出力用に1を代入
else
bit = 0;　　//0ならば出力用に0を代入
if((i % 4) == 0)　//ビット列を4つずつ区切る
printf(" ");

printf("%d",bit);
}
}

void lshift( unsigned int s, unsigned int e, unsigned int *el){
unsigned int er;

*el = e << s; //左にsシフト
er = e >> (N-s); //あふれるビット列を末尾に持ってくる
*el |= er; 　//左シフトとあふれたビット列のビット和をとる
/*左シフト回転の動作
例）入力 1111ffff
ビット表示 e: 0001 0001 0001 0001 1111 1111 1111 1111
3ビット左シフト er: 1000 1000 1000 1111 1111 1111 1111 1000
あふれるビットを末尾に持ってくる(32-3 = 29ビット右シフト)
*el: 0000 0000 0000 0000 0000 0000 0000 1000
*el | er: 1000 1000 1000 1111 1111 1111 1111 1000
*/
}

void rshift( unsigned int s, unsigned int e, unsigned int *er){
//右シフト回転
unsigned int el;

*er = e >> s; //右にｓシフト
el = e << (N-s); //あふれるビット列を先頭に持ってくる
*er |= el; 　//右シフトとあふれたビット列のビット和をとる

/*右シフト回転の動作
例）入力 1111ffff
ビット表示　　e: 0001 0001 0001 0001 1111 1111 1111 1111
3ビット右シフト*er: 0000 0010 0010 0010 0011 1111 1111 1111
あふれるビットを先頭に持ってくる(32-3 = 29ビット左シフト)
el: 1110 0000 0000 0000 0000 0000 0000 0000
　　　　 *er | el: 1110 0010 0010 0010 0011 1111 1111 1111
*/
}

数学未解決問題 part1

双子素数の問題
　2 と 3 の組を除くと、双子素数はもっとも数の近い素数の組である。ＰとＰ+２の両方が素数になるものを双子素数というとき双子素数は無限に存在するか?

　素数が無限に存在することは古代ギリシャから知られていたこととはうらはらに、双子素数は無限に存在するかという問題は長い間手に負えない問題であった。このいわゆる双子素数の予想や双子素数の問題と呼ばれる問題は、多くの数論学者が双子素数は無限に存在するだろうと予想しているにもかかわらず、2006年現在、いまだに数学上の未解決問題として残されている。
例）
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61),
(71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193),
(197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349),
(419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619),
(641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859),...
　二素数の場合にミレニアム問題でもあるゴールドバッハの予想が密接に絡んでくるため双方の研究が同時に進められてきた。2004年5月に、"Proof of Infinitely many Twin Primes" と題された論文が Richard Arenstorf によって提出された（末尾のリンクを参照）。この論文は上記のハーディ・リトルウッドの予想が正しいと主張するものであるが、内容に重大な誤りがあるとして著者自身によって撤回された。

"Proof of Infinitely many Twin Primes"

wikipedia

クドリャフカ (Кудрявка)

クドリャフカ (Кудрявка)
　クドリャフカまたはライカと呼ばれる犬がいる。1957年11月3日クドリャフカはスプートニック2号に乗ってバイコヌール宇宙基地から飛び立った。秒速8ｋｍという速度で飛び出したロケットはクドリャフカを衛星軌道上まで運んだ。元々スプートニック2号は大気圏突入が不可能な設計だったためロケットの中には安楽死できるよう毒入りのえさが載せられていた。こうしてクドリャフカは、衛星軌道に乗った初めての生き物となった。クドリャフカとは巻き毛の女の子の意味である、公式文書ではライカとされているが、当時の記録を見るにクドリャフカが正式名称であると考えられる。

　現代の宇宙開発・技術における進歩の裏にクドリャフカという子犬の犠牲があることは私たちは忘れてはならない。

現在クドリャフカをテーマとしたＦＬＡＳＨがあります。悲劇的に書かれていることが全て正しいとは限りません。クドリャフカが打ち上げられ死ぬまでの瞬間何を考え、思ったかは私たちにはわかりませんが、クドリャフカという子犬がいたということを皆さんの記憶に少しでも残ればと思います。

クドリャフカ(ＦＬＡＳＨ)

ロボット

　ロボット開発・研究が盛んになり、さまざまなロボットが世に出てきました。フューロや韓国で開発されたアインシュタインのようなロボット、走るロボットや押しても倒れないロボットなどいろいろな分野で使われ、そして研究されています。
　ここで私が注目したロボットBigDogについて話したいと思います。まずBigDogの開発目的は物の運搬です。特に悪路での円滑な運搬を主として開発されてきました。http://www.youtube.com/watch?v=RGrMMlNjBB8&search=bigdog