귀속 (一)

1 열: * 2 열: * * 3 열: * * 4 열: * * * *...N 열 에 있 는 * 의 개 수 를 구 합 니까?
우 리 는 1) 마지막 열, 그것 의 값 은 N 이라는 것 을 발견 했다.2) 총 개수 = N + 모든 남 은 열의 합.
public int triangle (int c) {return c + getCount (c - 1);} 이상 의 코드 는 잘못 되 었 습 니 다. 재 귀 에는 종료 조건 이 있어 야 합 니 다. 그렇지 않 으 면 무한 재 귀 되 어 프로그램 이 무 너 집 니 다.

 1 public class Triangle {

 2 

 3     public int triangle(int c) {

 4         if (c > 0) {

 5             int i = c - 1;

 6             return c + triangle(i);

 7         }

 8         return 0;

 9     }

10 

11     public static void main(String[] args) {

12         Triangle t = new Triangle();

13         System.out.println(t.triangle(4));

14     }

15 

16 }

인쇄 결과: 10
재 귀 방법의 특징: 1) 자신 을 호출 하 는 2) 자신 을 호출 할 때 이렇게 하 는 것 은 더 작은 문 제 를 해결 하기 위해 서 이다.3) 충분 하고 간단 한 문제 의 차원 이 존재 하 는데 이 층 의 알고리즘 에서 자신 을 호출 하지 않 아 도 직접 풀 수 있 고 결 과 를 되 돌려 줄 수 있다.
 
변위 문자:

 1 public class Anagram {

 2 

 3     static int size;

 4 

 5     static char[] arrChar;

 6 

 7     static int count;

 8 

 9     public static void main(String[] args) {

10         String input = "cats";

11         arrChar = input.toCharArray();

12         size = arrChar.length;

13         doAnagram(size);

14     }

15 

16     public static void doAnagram(int newSize) {

17         if (newSize == 1) {

18             return;

19         }

20         for (int i = 0; i < newSize; i++) {

21             doAnagram(newSize - 1);

22             if (newSize == 2)

23                 display();

24             rotate(newSize);

25         }

26     }

27 

28     public static void display() {

29         System.out.print(++count + " : ");

30         for (int i = 0; i < size; i++) {

31             System.out.print(arrChar[i]);

32         }

33         if (count % 6 == 0) {

34             System.out.println();

35         }

36         else {

37             System.out.print("\t");

38         }

39     }

40 

41     public static void rotate(int newSize) {

42         int j;

43         int position = size - newSize;

44         char temp = arrChar[position];

45         for (j = position + 1; j < size; j++) {

46             arrChar[j - 1] = arrChar[j];

47         }

48         arrChar[j - 1] = temp;

49     }

50 

51 }

인쇄 결과: 1: cats 2 : cast 　　  3 : ctsa 　    4 : ctas 　 　 5 : csat 　　  6 : csta 7 : atsc 　　  8 : atcs　　   9 : asct 　　 10 : astc 　　11 : acts 　　12 : acst13 : tsca 　　14 : tsac 　　15 : tcas 　　16 : tcsa 　　17 : tasc 　　18 : tacs　　19 : scat 　　20 : scta 　　21 : satc 　　22 : sact　　 23 : stca 　　24 : stac
 
재 귀적 2 분 검색: 재 귀적 2 분 검색 과 비 재 귀적 2 분 검색 역시 큰 O 효율 입 니 다. O (logN), 재 귀적 인 2 분 검색 은 간결 하지만 속도 가 느 릴 수 있 습 니 다.

 1 public class OrderArray {

 2 

 3     private long[] array;

 4 

 5     private int maxLength;

 6 

 7     public OrderArray(int size) {

 8         array = new long[size];

 9         maxLength = 0;

10     }

11 

12     //       ，    。

13     public void insert(long l) {

14         int i;

15         for (i = 0; i < maxLength; i++) {

16             if (array[i] > l) {

17                 break;

18             }

19         }

20         for (int j = maxLength; j > i; j--) {

21             array[j] = array[j - 1];

22         }

23         array[i] = l;

24         maxLength++;

25     }

26 

27     //    

28     public int find(long key) {

29         int lower = 0;

30         int upper = maxLength - 1;

31         int index;

32         while (true) {

33             index = (lower + upper) / 2;

34             if (array[index] == key) {

35                 return index;

36             }

37             else if (lower > upper) {

38                 return -1;

39             }

40             else {

41                 if (array[index] < key) {

42                     lower = index + 1;

43                 }

44                 else {

45                     upper = index - 1;

46                 }

47             }

48         }

49     }

50 

51     public int recFind(long key) {

52         return recFind(key, 0, maxLength - 1);

53     }

54 

55     //      

56     private int recFind(long key, int lower, int upper) {

57         int index = (lower + upper) / 2;

58         if (array[index] == key) {

59             return index;

60         }

61         else if (lower > upper) {

62             return -1;

63         }

64         else {

65             if (array[index] < key)

66                 lower = index + 1;

67             else

68                 upper = index - 1;

69             return recFind(key, lower, upper);

70         }

71     }

72 

73     public void display() {

74         for (int i = 0; i < maxLength; i++) {

75             System.out.println("NO." + (i + 1) + " --> " + array[i]);

76         }

77     }

78 

79 }

 1     public static void main(String[] args) throws ParseException, InterruptedException {

 2         OrderArray array = new OrderArray(100);

 3 

 4         array.insert(49);

 5         array.insert(158);

 6         array.insert(81);

 7         array.insert(93);

 8         array.insert(18);

 9         array.insert(1);

10         array.insert(9);

11         array.insert(7);

12         array.insert(81);

13         array.insert(669);

14         

15         array.display();

16         

17         int key = 18;

18         System.out.println(key + " is NO " + (array.recFind(key)+1));

19     }

인쇄 결과: NO. 1 -- > 1NO. 2 -- > 7NO. 3 -- > 9NO. 4 -- > 18NO. 5 -- > 49NO. 6 -- > 81NO. 7 -- > 81NO. 8 -- > 93NO. 9 -- > 158 NO. 10 -- > 66918 is NO 4