初心者アルゴリズム入門(ブルーブリッジカップの選抜試合)

60498 ワード
初心者アルゴリズム
c言語版の
一回の校内の小さいテストのテーマ、暇な时に用事がなくてやりました..ある問題には完全な問題がないが,結局私は盗んだのだ.しかし、すべてネット上で选ぶテーマなので、あまり影响しません!!
1.自然数nを入力し、n以下の素数の和を求める
    

#include 
int judge(int);
int main(void) {
	int n,i,count = 3;
	scanf("%d",&n);
	if(n==1){
		printf("1");
	}
	else if(n==2){
		printf("3");
	}else{
		for(i = 3;i<=n;i++){
			if(judge(i)){
				count+=i;
			}
		}
		printf("%d",count);
	}
	return 0;
}
//       
int judge(int n){
	int i;
	for(i = 2;i<n;i++){
		if(n%i==0){
			break;
		}
	}
	if(i==n){
		return 1;
	}
	return 0;
}

2.各ビットを満たすすべてのキューブを小さいから大きいまで出力し、自分の10進数3桁に等しい(1行1個)
遍歴する
#include 
int main(){
	int i,a,b,c;
	for(i =100;i<999;i++){
		a = i%10;
		b = (i/10)%10;
		c = i/100;
		if(a*a*a+b*b*b+c*c*c==i){
			printf("%d
",i);
		}
	}
	return 0;
}

3.配列の中の最大値を探す(配列で作ることを制限してそれではまたどんなhhhaO(∩∩)Oを使うことができます)
最初の行にnを入力し、nの数字を入力します.
出力:1行目は入力したn個の数字を出力し、2行目はn個の数字の中の最大値を出力する
​ 
#include 
int main(){
	int i,n,a[10000],max=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		printf("%d ",a[i]);
		if(a[i]>max){
			max = a[i];
		}
	}
	printf("
%d",max);
	return 0;
}

4.文字列(長さ100以内)を入力し、数値文字の出現回数を集計します.
#include 
int main() {
	char str[100];			//100    
	int i = 0,count=0;
	scanf("%s",str);
	while(str[i]){			//        
        if(str[i]>='0'&&str[i]<='9'){
            count++;
        }
        i++;
	}
	printf("%d",count);
}

5.3行4列の絶対値の最大数を出力し、行と列を改行して出力します.(注意絶対値最大の数が負数の場合の出力も負数)
この問題は上の問題と最大値を探すのと大同小異だ.負数を正数に変換して比較する場合は、出力時に元の数字を出力することを覚えておく必要があります.
#include 
int main(){
	int i,j,max=0,a,b,c=0; //a，b        （      1）
	int arr[3][4];
	for(i=0;i<3;i++){
		for(j =0;j<4;j++){
			scanf("%d",&arr[i][j]);
			if(arr[i][j]<0){
				arr[i][j]=0-arr[i][j];
				c = 1;
				if(arr[i][j]>max){
					max = arr[i][j];
					a = i;
					b =j;
					c = 1;       // c             
				}
			}
			else{
				if(arr[i][j]>max){
					max = arr[i][j];
					a = i;
					b =j;
					c = 0;
				}
			}

		}
	}
	if(c == 1){               //   。
		printf("%d
",-max);
	}else{
		printf("%d
",max);
	}
	printf("%d %d",a+1,b+1);  //   1   
	return 0;
}

6.m個の返却靴を持っている人、n個の貸し靴を持っている人(列に並んでいる)は、靴を借りるたびに靴が借りられることを保証しなければならない.
m,nを入力すると,それぞれ靴を返すことと靴を借りることを示し,満足できるすべての列数を出力する.(2つの返却靴の位置は区別されません)
​
各配列について:
  • 靴を返す人数が靴を借りる人数より少ない場合、満足できず、0
    • に戻る
  • 靴を借りる人数が0の場合、1つの並べ方しかありません.
  • m+n人の中から、出てきて一人が最初の位置に置いて、残りのm+n-1人を並べます.
  • 出てきた人が靴を借りるときf(m,n-1)
  • が靴返却の場合f(m-1,n)
  • だからm+n個人の並べ方はf(m-1,n)+f(m,n-1)である.

    • 再帰的な実装:
    #include 
int judge(int m ,int n){
	if(n==0){
		return 1;
	}
	if(m<n||m==0){
		return 0;
	}
	return judge(m-1,n)+judge(m,n-1);
}
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%d",judge(m,n));
	return 0;
}

    もう一つの書き方
    #include
#define x 18
int main()
{
    int arr[x][x]={0};
    for(int i=1;i<x;++i)
    {
        arr[i][0]=1;
        for(int j=1;j<=i;++j)
        {
            arr[i][j]=arr[i-1][j]+arr[i][j-1];
        }
    }
    int n,m;
    scanf("%d%d",&n,&m);
    printf("%d",arr[n][m]);
    return 0;
}

    [原句]李白が酒を飲む(テーマが長すぎる…)
    深さ検索...再帰を使用します.
  • は2つの状況に分かれています.花に出会ったり、店に出会ったりします.
  • 花に出会った回数と店に出会った回数がいずれも題意を満たす場合、酒も題意を満たし、再帰を終了し、カウントを1加算する.
  • 酒が不足したり、店や花に出会った回数が問題を満たしていない場合return.(再帰終了条件)
    • #include 
int count=0;
void judge(int a ,int b , int w){
	if(a==0&&b==1){  //  0   1（       ）
		if(w==1){     //  1
			count++;   
		}
		return;     
	}
	if(a<0||b<0||w<0){ //    return
		return;
	}
	judge(a-1,b,2*w);  //   
	judge(a,b-1,w-1);  //   
}
int main(){
	judge(5,10,2);
	printf("%d",count);
	return 0;
}

    8.炒め物を習う
    この問題は比較的に簡単で(前の2つの問題O(∩∩)O)に比べて)、とても理解しやすいです
    最初の料理から順に1回通して、必要な材料を見つけて、それぞれの材料が満たされている場合(>0)、料理数が1つ増えて、1つの材料が満たされていない場合は次の料理のスキャンを行います.
    #include

int main () {
	int a,b,c,d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	int s = 0;
	switch(1){
		case 1:
			while(1){
				if(a >= 2 && b >= 1 && d >= 2){
					a -= 2;
					b -= 1;
					d -= 2;
					s ++;
				} else {
					printf("%d
    "    ,s);
					s = 0;
					break;
				}
			}
		case 2:
			while(1){
				if(a >= 1 && b >= 1 && c >=1 && d >= 1){
					a -= 1;
					b -= 1;
					c -= 1;
					d -= 1;
					s ++;
				} else {
					printf("%d
    "    ,s);
					s = 0;
					break;
				}
			}
		case 3:
			while(1){
				if(c >= 2 && d >= 1){
					c -= 2;
					d -= 1;
					s ++;
				} else {
					printf("%d
    "    ,s);
					s = 0;
					break;
				}
			}
		case 4:
			while(1){
				if(b >= 3){
					b -= 3;
					s ++;
				} else {
					printf("%d
    "    ,s);
					s = 0;
					break;
				}
			}
		case 5:
			while(1){
				if(a >= 1 && d >= 1){
					a -= 1;
					d -= 1;
					s ++;
				} else {
					printf("%d
    "    ,s);
					s = 0;
					break;
				}
			}
	}
	return 0;
}

    実は
    最後の問題のcコードは私のネット上でコピーしたのです.の
    最初はjavaで書いたので、この問題も友好的でした.cで書くのがおっくうだ(主にcのレベルが低すぎるO(∩∩)O).
    私が書いたjavaコードは以下の通りです.
    import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		
		String[]str = {"aabdd","abcd","ccd","bbb","ad"};
		int[]result = new int[5];
		int[]arr = new int[4];
		Scanner sc = new Scanner(System.in);
		for(int i=0;i<4;i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i =0;i<str.length;i++) {
			char[] ch = str[i].toCharArray();
			arr = judge(ch,arr);
			if(judge(arr)) {
				result[i]++;
			}
			else {
				arr = plus(ch,arr);
			}
		}
		for(int i =0;i<result.length;i++) {
			System.out.println(result[i]);
		}
		sc.close();
	}
	
	static int[] judge(char[]ch,int[]arr) {
		for(int i =0;i<ch.length;i++) {
			if(ch[i]=='a') {
				arr[0]--;
			}
			if(ch[i]=='b') {
				arr[1]--;
			}
			if(ch[i]=='c') {
				arr[2]--;
			}
			if(ch[i]=='d') {
				arr[3]--;
			}
		}
		return arr;
	}
	static int[] plus(char[]ch,int[]arr) {
		for(int i =0;i<ch.length;i++) {
			if(ch[i]=='a') {
				arr[0]++;
			}
			if(ch[i]=='b') {
				arr[1]++;
			}
			if(ch[i]=='c') {
				arr[2]++;
			}
			if(ch[i]=='d') {
				arr[3]++;
			}
		}
		return arr;
	}
	static boolean judge(int[]arr) {
		for(int i=0;i<arr.length;i++) {
			if(arr[i]<0) {
				return false;
			}
		}
		return true;
	}

}

    の最後の部分
    私のブログへようこそ:bliziのブログ»
    GCE から Google Cloud SQL への接続方法
    [剣指offer]2 D配列での検索