「AOJ Problem Set from ALDS1問　0～19」の編集履歴（バックアップ）一覧に戻る

AOJ Problem Set from ALDS1問　0～19 - (2014/01/12 (日) 17:00:04) のソース

会津大学オンラインジャッジ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
ｇｃｄを実装する問題。
指定通り実装するだけです。


 #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));
 }