1. 소개
저자는 대학의 알고리즘 경쟁에서 그러한 질문에 직면했습니다. 이제 나는 당신과 공유 할 것입니다 : 8 개의 은화 Abcdefgh가 있으며 그 중 하나는 실제 통화와는 다른 위조 통화로 알려져 있지만, 그것이 더 가볍거나 무겁는지는 모르겠습니다. 균형을 사용하여 최소 비교 수와 위조 통화가 어떤 동전을 결정하는지, 그리고 위조 통화가 실제 통화보다 가볍거나 무겁다는 것을 알고 있습니다.
2. 분석
이 질문이 어떤 위조 통화가 매우 간단한 지 해결하는 것이라면 문제는 그다지 복잡하지 않으며 결과를 얻기 위해 되돌아 가면 되돌아 가면됩니다. 문제의 어려움을 처리하기 위해 최소한 단계를 사용해야합니다! ! !
이전 데이터 구조 문제와 비교하여 재귀 및 역 추적이 있습니다. 오늘날 우리는 Tree라는 새로운 개념과 접촉해야 할 수도 있습니다. 이름에서 알 수 있듯이 숫자 구조는 분석 다이어그램이 브랜치 노드와 같은 다양한 정보를 가진 트리와 같음을 의미합니다. 트리 구조는 우리의 논의가 아니라 데이터 구조에서 더 큰 장입니다. 이 질문에서, 우리는 나무의 소분자 인 의사 결정 트리를 소개 할 것입니다.
먼저 8 개의 은화를 해결하기위한 수학적 모델을 구축합시다. 간단한 상황은 다음과 같습니다. 우리는 은화 ABCDEFG 등을 지명합니다. 차례로 A+B+C와 D+E+F를 비교합니다. 그것이 같으면 위조 통화는 g 또는 h 여야합니다. 우리는 먼저 어느 것이 더 무겁고, g 또는 h인지 비교합니다. g가 더 무겁면 A와 비교하십시오 (A는 실제 통화입니다). G가 A와 같으면 G는 실제 통화이고 H는 가짜 통화입니다. H는 G보다 가볍고 G는 실제 통화이므로 위조 통화의 무게는 실제 통화보다 가볍습니다.
동일하지 않으면 어떻게됩니까? 뭐야? 우리는 최종 답변을 얻을 때까지 가지를 차례로 비교할 것입니다!
3. 샘플 다이어그램
위의 분석을 바탕으로 완전한 의사 결정 트리 다이어그램을 가질 수 있습니다.
4. 코드
공개 클래스 코인 {private int [] 코인; 공개 코인 () {코인 = 새로운 int [8]; (int i = 0; i <8; i ++) 코인 [i] = 10; } public void setfake (int weight) {코인 [(int) (math.random () * 7)] = 무게; } public void fake () {if (코인 [0]+동전 [1]+코인 [2] == 코인 [3]+동전 [4]+코인 [5]) {if (코인 [6]> 코인 [7]) 비교 (6, 7, 0); 그렇지 않으면 비교 (7, 6, 0); } else if (코인 [0]+동전 [1]+동전 [2]> 코인 [3]+동전 [4]+코인 [5]) {if (코인 [0]+코인 [3] == 코인 [1]+코인 [4]) 비교 (2, 5, 0); 그렇지 않으면 (코인 [0]+동전 [3]> 동전 [1]+코인 [4]) 비교 (0, 4, 1); if (코인 [0]+코인 [3] <코인 [1]+코인 [4]) 비교 (1, 3, 0); } else if (코인 [0]+코인 [1]+동전 [2] <코인 [3]+코인 [4]+코인 [5]) {if (코인 [0]+코인 [3] == 코인 [4]) 비교 (5, 2, 0); 그렇지 않으면 (코인 [0]+동전 [3]> 동전 [1]+코인 [4]) 비교 (3, 1, 0); if (코인 [0]+코인 [3] <코인 [1]+코인 [4]) 비교 (4, 0, 1); }} Protected Void Compar (int i, int j, int k) {if (coins [i]> coins [k]) system.out.print ( "/nfake coins" + (i + 1) + "heavier"); else system.out.print ( "/n 가짜 통화" + (j + 1) + "라이터"); } public static void main (String [] args) {if (args.length == 0) {System.out.println ( "입력 가짜 통화 중량 (10)"); System.out.println ( "Ex. Java Coins 5"); 반품; } 코인 8 코인 = 새로운 동전 (); 8coins.setfake (integer.parseint (args [0]); 8coins.fake (); }}결과:
위조 통화 중량을 입력하십시오 (10보다 크거나 작음)
전. 자바 동전 5
다음은 일반적인 문제 해결 방법입니다. 코드를 신중하게 고려할 수 있습니다. 이 코드의 경우 위의 분석으로 충분합니다. 모든 사람은 그것에 대해 생각하고 나머지를 스스로 배워서 깊이 이해할 수 있어야합니다.
요약
위의 것은 Java 프로그래밍 구현을위한 8 개의 Silver Coins 코드를 해결하는 것에 대한이 기사의 모든 내용입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!