ループ


1.ループとは?


  • ループ(再帰)または再帰呼び出しは、あるアルゴリズムまたは関数呼び出し自身が問題を解決するためのプログラミングテクニックです.

  • たとえば、整数のファクトリ(factorial)は、次のように定義されます.


  • 上の定義でfactorial(n!)階乗を再定義(n-1)!この使われているものに注目してみましょう.この定義をループと呼ぶ.
  • #include<stdio.h>
    int factorial(int n){//순환적인 팩토리얼 계산 함수
    	if(n==1){// n==1일 경우  
    		return 1;
    	}
    	else{//n>1일 경우  
    		return (n*factorial(n-1));
    	}
    }	
    int main(){
    	printf("5! : %d",factorial(5));
    }

    2.重複する工場計算関数


    次の例
  • を使用すると、ループをより迅速に使用することができる.
  • #include<stdio.h>
    int factorial_iter(int n){
    	int k, result=1;
    	for(k=n;k>0;k--){
    		result *= k;
    	}
    	return result;
    }	
    int main(){
    	printf("5! : %d",factorial_iter(5));
    }

    3.循環アルゴリズムの性能

  • 上のプラント例では、反復およびサイクルの性能が分析される.反復アルゴリズムの時間的複雑さはどのくらいですか?forを用いてn回繰り返し,時間複雑度はO(n)であった.
  • 工場でサイクルアルゴリズムを実現する時間の複雑さは、サイクルでは、呼び出しごとに乗算が実行され、サイクル全体がn回呼び出されるため、O(n)である.
  • 4.フィボナッチ数列の計算

  • フィボナッチ数列の定義
  • int fib(int n){//피보나치 수열의 순환적 호출
    	if(n==0)
    		return 0;
    	if(n==1)
    		return 1;
    	return (fib(n-1)+fib(n-2));
    }
  • 上の関数は簡単で分かりやすいが、非常に非効率である.ループが繰り返されるほど,nが大きくなるほど,大量のループ呼び出しが必要となる.
  • int fib_iter(int n){
    	int i,tmp,current,last;
    	if(n<2)
    		return n;
    	else{
    		last=0;
    		current=1;
    		for(int i=2;i<=n;i++){
    			tmp = current;
    			current += last;
    			last = tmp;
    		}
    		return current;
    	}
    }

    5.ハノイタワー


    1)ハノイタワー規則


    円板
  • は一度に1枚しか移動できません
  • の上部の円板だけが
  • を移動することができます.
  • の大きさの円板には大きな円板を積むことはできません.
  • の間の棒を一時的に使うことができますが、前の条件を守らなければなりません.
  • #include<stdio.h>
    void hanoi_tower(int n,char from, char tmp, char to){
    	if(n==1){
    		printf("원판 1을 %c에서 %c로 옮긴다.\n",from,to);
    	}
    	else{
    		hanoi_tower(n-1,from,to,tmp);
    		printf("원판 %d을 %c에서 %c으로 옮긴다.\n",n,from,to);
    		hanoi_tower(n-1,tmp,from,to);
    	}
    }
    void main(){
    	hanoi_tower(4,'A','B','C');
    }