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

AOJ Problem Set from ALDS1問　0～19 - (2014/01/12 (日) 17:49:57) の編集履歴(バックアップ)

---

会津大学オンラインジャッジ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));
}

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