पास्कल में बैकट्रैकिंग: अधिकतम भारित शाखा

Question

मैं पास्कल (फ्री पास्कल कंपाइलर का उपयोग करके) एक हफ्ते के लिए सीख रहा हूं, और एक आसान अभ्यास में आया।

1 
    4 9 
    7 0 2 
4 8 6 3 

एक शाखा संख्या के किसी भी क्रम है, ऊपर से शुरू (इस मामले में: 1), जब हर नंबर के लिए शाखा नीचे विस्तार कर सकते हैं या तो जैसा कि नीचे दिखाया एक संरचना को देखते हुए अधिक से अधिक भारित शाखा लगता है बाएं या नीचे दाएं। उदाहरण के लिए, शाखा 1-4-0 या तो 1-4-0-8 या 1-4-0-6 में विस्तार कर सकती है। सभी शाखाओं को शीर्ष से शुरू होना चाहिए और नीचे अंत में होना चाहिए।

इस उदाहरण में, अधिकतम शाखा 1-4-7-8 है, जो हमें 20 देती है। इस प्रश्न को हल करने के लिए, मैंने बैकट्रैकिंग का उपयोग करने की कोशिश की। त्रिकोणीय संरचना प्रकार 'त्रिकोण' की एक सरणी में संग्रहीत किया गया था:

type triangle = array[1..MAX_NUM_OF_ROWS, 1..MAX_NUM_OF_ROWS] of integer; 

यहाँ मेरी कार्यान्वयन है:

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; 
begin 
if i = dim then 
    findAux := data[i][j] 
else 
    if findAux(data, dim, i + 1, j + 1) > findAux(data, dim, i + 1, j) then 
     findAux := data[i+1][j+1] + findAux(data, dim, i + 1, j + 1); 
    else 
     findAux := data[i+1][j] + findAux(data, dim, i + 1, j); 
end; 

function find_heaviest_path(data: triangle; dim: integer) : integer; 
begin 
    find_heaviest_path := findAux(data, dim, 1, 1); 
end; 

आप देख सकते हैं, मैं एक सहायक समारोह का उपयोग किया है। दुर्भाग्य से, यह सही परिणाम नहीं लग रहा है। ऊपर देखी गई संरचना के लिए, परिणाम मुझे 27 है, जो 7 अंक बंद है। मैं क्या खो रहा हूँ? कार्यान्वयन समग्र रूप से कैसे दिखता है? मुझे यह जोड़ना चाहिए कि इस अभ्यास के लिए पंक्तियों की अधिकतम संख्या 100 है। यदि स्पष्टीकरण की आवश्यकता है, तो कृपया पूछने में संकोच न करें।

Answer 1

आपका findAux पुनरावर्ती प्राप्त परिणाम के लिए गलत मान जोड़ रहा है। एक तरफ के रूप में, आप कुछ स्थानीय चर का उपयोग कर कोड को थोड़ा सा साफ कर सकते हैं। findAux का एक सही संस्करण:

uses math; 

... 

function findAux(data: triangle; dim: integer; i: integer; j:integer) : integer; 
var 
    left, right: integer; 
begin 
    if i = dim then 
     findAux := data[i][j] 
    else begin 
     left := findAux(data, dim, i + 1, j); 
     right := findAux(data, dim, i + 1, j + 1); 
     findAux := data[i][j] + Max(left, right); 
    end; 
end;