잔돈 교환, C 언어 환전 문제, 2 가지 해법, 5 가지 최적화, 동적 계획 + 동적 배열

 
환전 문제, C 언어, 2 가지 해법, 6 가지 최적화, 동적 계획 + 동적 배열
신인 이 처음으로 글 을 올 렸 는데, 조판 찌꺼기 는 양해 해 주 십시오.
c 언어 를 배 운 지 한 달 이 되 었 습 니 다. 기술 알고리즘 수준 이 높 지 않 습 니 다. 문제 가 있 으 면 지적 해 주 십시오. 감사합니다.
제목: n 원 을 주 고 n 원 을 1, 5, 10, 20, 50, 100 액면가 로 구 성 된 돈 으로 바 꾸 고 얼마나 많은 교환 방법 을 구 합 니까?
1 폭력, 간단 하고 거 친, 모든 액면가 의 상황 을 시험 해 보 세 요. 조건 에 맞 는 자체 증가, 테스트 n = 20 결 과 는 1 초 정도 나 옵 니 다.

#include
#include
int main()
{
	int n,m;
	while(scanf("%d",&n)!=EOF)
	{
		m=0;
    	for(int i1=0;i1<=n;++i1){
    	    for(int i2=0;i2<=n;++i2){
        	    for(int i3=0;i3<=n;++i3){
            	    for(int i4=0;i4<=n;++i4){
                	    for(int i5=0;i5<=n;++i5){
                    	    for(int i6=0;i6<=n;++i6){
                        		if(n==100*i6+50*i5+20*i4+10*i3+5*i2+i1){
                            	++m;
                            	//printf("  %d：100 ：%d  50 ：%d  20 ：%d  10 ：%d  5 ：%d  1 ：%d 
",m,i6,i5,i4,i3,i2,i1);
							}
					   }
                   }
               }
           }
        }    
    }
    printf("%d
",m);
	}
return 0;
}
2  ，      ，                  ，       ，  n=200    1   
#include
int main()
{
	int n,m;
	while(scanf("%d",&n)!=EOF)
	{
		m=0;
    	for(int i1=0;i1<=n;++i1){
           	for(int i2=0;i2<=(n-i1)/5;++i2){
               	for(int i3=0;i3<=(n-i1-i2*5)/10;++i3){
                	for(int i4=0;i4<=(n-i1-i2*5-i3*10)/20;++i4){
                		for(int i5=0;i5<=(n-i1-i2*5-i3*10-i4*20)/50;++i5){
                 			for(int i6=0;i6<=(n-i1-i2*5-i3*10-i4*20-i5*50)/100;++i6){
                       			if(n==100*i6+50*i5+20*i4+10*i3+5*i2+i1){
                           			++m;
                           			//printf("  %d：100 ：%d  50 ：%d  20 ：%d  10 ：%d  5 ：%d  1 ：%d 
",m,i6,i5,i4,i3,i2,i1);
								}
							}
                   	    }
               	    }
           	    }
       	    }	    
	    }
	    printf("%d
",m);
	}
	return 0;
}

3    ，        ，                       ，      1      ，
        1 5      ，      1 、5  10      ，    ，
  6 ，  n=10 ，     temp[0~9]=1，     temp[0~4]=   1,temp[5~9]=   1+1=2,
temp[10]=   2+1=3
#include 
int main()
{
	int a[6]={1,5,10,20,50,100},n;
	while(scanf("%d",&n)!=EOF)
	{
		int temp[10000]={0};
		temp[0]=1;
		for(int i=0;i<6;i++){
			for(int j=1;j<=n;j++){
				if(j>=a[i])
					temp[j]+=temp[j-a[i]];
			//printf("%d
",temp[j]);
			}
		//	printf("
");
		}
		printf("%d
",temp[n]);
	}
	return 0;
}

4    ，            j      1  ，    1~a[i]-1        if   ，
        ，               a[i]      j a[i]    ，        if    ，     
#include 
int main()
{
	int a[6]={1,5,10,20,50,100},n;
	while(scanf("%d",&n)!=EOF)
	{
		int temp[10000]={0};
		temp[0]=1;
		for(int i=0;i<6;i++){
			for(int j=a[i];j<=n;j++){
			//	if(j>=a[i])
					temp[j]+=temp[j-a[i]];
			//printf("%d
",temp[j]);
			}
		//	printf("
");
		}
		printf("%d
",temp[n]);
	}
	return 0;
}

5    +    
        a[10000]  ，  n>=10000  ，    ，
             ，   n    ，           ，n     n+1   

      
#include //     
int *a;
int N;
scanf("%d", &N);//      
a = (int *) malloc(N * sizeof(int));//    
....
free(a);//    


     

#include 
#include
int main()
{
	int a[6]={1,5,10,20,50,100},n;
	while(scanf("%d",&n)!=EOF)
	{
		int *temp=(int*)malloc(sizeof(int)*(n+1));//n+1    temp[j]  
		temp[0]=1;
		for(int i=0;i<6;i++)
			for(int j=a[i];j<=n;j++)
					temp[j]+=temp[j-a[i]];
		printf("%d
",temp[n]);
		free(temp);
	}
	return 0;
}
  int  -2~31 2~31，  int  2147483647，     n 4094 4095，4096 int  

6    +    +      
      ，        long long，      n     
#include 
#include
int main()
{
	int a[6]={1,5,10,20,50,100},n;
	while(scanf("%d",&n)!=EOF)
	{
		long long *temp=(long long*)malloc(sizeof(long long)*(n+1));
		temp[0]=1;
		for(int i=0;i<6;i++)
			for(int j=a[i];j<=n;j++)
					temp[j]+=temp[j-a[i]];
		printf("%lld
",temp[n]);
		free(temp);
	}
	return 0;
}