会津大学オンラインジャッジALDS 問0~20まで *Getting Started - Insertion Sort 挿入ソートのステップを表示していく問題。 解法 挿入ソートが何をしているかイメージできたら何の問題もない問題です。 要は数字列を左から整列していき、右へ進むだけです。 右で新しい数字が来たら左にさかのぼって入れる位置を決め、そこまでにいる数を全て右へ一つずつずらします。 #include<stdio.h> static const int N = 1000; void trace(int A[], int n){ int i; for ( i = 1; i <= n; i++ ){ if ( i > 1 ) printf(" "); printf("%d", A[i]); } printf("\n"); } int main(){ int n, i, j; int A[N+1]; scanf("%d", &n); for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]); trace(A, n); for(int j=2;j<=n;j++){ int key=A[j]; i=j-1; while(i > 0 && A[i]>key){ A[i+1]=A[i]; i--; } A[i+1]=key; trace(A,n); } return 0; } *Getting Started - Greatest Common Divisor http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B gcdを実装する問題。 指定通り実装するだけです。 #include<stdio.h> int gcd(int a,int b){ int c; while(a!=0){ c=a; a=b%a; b=c; } return b; } int main(){ int a,b; scanf("%d %d",&a,&b); printf("%d\n",gcd(a,b)); } *Getting Started - Prime Numbers http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C 与えられた数列の中に素数が何個あるか答える問題。 解法 1億までの数しか数列に現れないので、10000までの素数で試し割すれば素数かどうか判別できます。 10000までの素数の列は篩で求めます。 #include<stdio.h> #include<vector> std::vector<int> prime_list; void calc_prime_list(){ int is_prime[10001]={0}; for(int i=2;i<400;i++){ if(is_prime[i]==1)continue; for(int j=i*2;j<10001;j+=i){ is_prime[j]=1; } } for(int i=2;i<10001;i++){ if(is_prime[i]==0)prime_list.push_back(i); } } bool prime_check(int n){ for(int i=0;i<prime_list.size();i++){ int p=prime_list[i]; if(p*p>n)break; if(n%p==0)return false; } return true; } int main(){ calc_prime_list(); int n,ans=0,num; scanf("%d",&n); while(n--){ scanf("%d",&num); ans+=prime_check(num); } printf("%d\n",ans); } *Sort I - Bubble Sort http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A 指定通りソートを記述するだけ。 数列の右端から初めて左端へ進みながら小さい数を選んで左右を入れ替えていく。 すると最初の右から左への一巡で、一番小さい数が左端にくる。 あとはそれから左端一個除いた部分で同じ処理を繰り返しこれを繰り返すと最後は全部ソートされる。 #include<stdio.h> void print(int A[],int n){ for(int i=1;i<n;i++)printf("%d ",A[i]); printf("%d\n",A[n]); } int main(){ int A[102],n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&A[i]); for(int i=1;i<=n;i++){ for(int j=n;j>i;j--){ if(A[j]<A[j-1]){ int t=A[j-1]; A[j-1]=A[j]; A[j]=t; ans++; } } } print(A,n); printf("%d\n",ans); } *Sort I - Selection Sort http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B 選択ソートを実装しソートの交換回数をこたえる問題。 選択ソートはまず配列を全部見て、一番小さいものを左端に持ってくる。 すると左端は一個でソートされ一番小さいものが左端に来て、残りは未ソートです。 2個めから全部精査しその中で一番小さいものを左から2番目に持ってくれば。 左は一番小さいものが左端に、その次に小さいのが左から2番目とこれを繰り返せばすべてソートされます。 #include<stdio.h> void print(int A[],int n){ for(int i=1;i<n;i++)printf("%d ",A[i]); printf("%d\n",A[n]); } int main(){ int A[102],n,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&A[i]); for(int i=1;i<=n;i++){ int mini=i; for(int j=i;j<=n;j++){ if(A[j]<A[mini]){ mini=j; } } if(i!=mini){ int t=A[i]; A[i]=A[mini]; A[mini]=t; ans++; } } print(A,n); printf("%d\n",ans); } *Sort I - Stability http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C バブルソートと選択ソートを行いそれがソート結果が安定であったかどうか判定する問題。 解法 バブルソートは無条件で安定なので常にStableです。 選択ソートは左側を決めてそれと入れ替える数を右側で探す際。 最初に入れ替える数と同じ数が出会った場所をPとし。 そのPより右側で最も小さい数が見つかった場合安定でなくなります。 #include<stdio.h> #include<algorithm> #include<string.h> void print(char A[37][3],int n){ for(int i=1;i<n;i++)printf("%s ",A[i]); printf("%s\n",A[n]); } void BubbleSort(char A[37][3],int n){ for(int i=1;i<=n;i++){ for(int j=n;j>i;j--){ if(A[j][1]<A[j-1][1]){ std::swap(A[j-1][0],A[j][0]); std::swap(A[j-1][1],A[j][1]); } } } print(A,n); printf("Stable\n");//バブルソートは常に安定 } void SelectionSort(char A[37][3],int n){ bool isStable=true; for(int i=1;i<=n;i++){ int mini=i,p; p=mini; for(int j=i;j<=n;j++){ if(A[j][1]<A[mini][1]){ mini=j; }else if(A[j][1]==A[i][1]&&i==p){ p=j; } } if(i!=mini){ std::swap(A[i][0],A[mini][0]); std::swap(A[i][1],A[mini][1]); if(i<p&&p<mini)isStable=false; } } print(A,n); printf("%s\n",isStable?"Stable":"Not stable"); } int main(){ int n; char A[37][3],B[37][3]; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",A[i]); } memcpy(B,A,sizeof(A)); BubbleSort(A,n); SelectionSort(B,n); }