java - penilaian berbilang pokok, tuan program dan tuan algoritma harus melihat

Question

Saya menghadapi soalan ujian bertulis dan saya tidak tahu sama sekali. Sila minta bantuan. . . .

Kelas yang diketahui ditakrifkan seperti berikut

class Node {
    public Double value;
    public List<Node> children;
}

Nod input memenuhi syarat berikut:
1 Nilai nod ialah nombor titik terapung lebih besar daripada 0
2 Nilai nod bawahan nod (dan nod peringkat bawah) mungkin nol atau nombor titik terapung lebih besar daripada 0
Fungsi program adalah seperti berikut:
1 akan Semua nilai dalam struktur pokok yang nol ditetapkan kepada nombor titik terapung yang lebih besar daripada 0
2 Nilai nod bukan daun (iaitu, nod dengan bilangan kanak-kanak yang lebih besar daripada 0) adalah sama dengan jumlah nilai anak-anaknya

public void doit(Node node){
    ......
}

Contoh

Jawapan

Bagaimana untuk menjawab soalan ini?

Sesetengah pakar telah menjawabnya dengan menggabungkan jawapan dua orang di bawah adalah jawapan yang sempurna. Malah, jika saya menerima pakai jawapan dan menukar taburan yang sama kepada rawak, ia akan menjadi sempurna

Answer 1

Saya belum menulis sebarang kod khusus, tetapi mari kita bercakap tentang idea itu
Pertama, bahagikan masalah kepada 2 langkah
Langkah1 Tentukan nilai nod bukan daun
Langkah2 Tentukan nilai nod daun
Langkah Proses1 pertama. Selepas Step1 diproses, tidak perlu Step2 Seperti yang saya katakan, bahagikan sama rata mengikut nilai nod induk.
Untuk Langkah1,
langkah1-1: Lintas setiap nod bukan daun dari bawah ke atas, dan tentukan nilai minimumnya dengan menjumlahkan nod anaknya. Sebagai contoh, subpokok paling kanan mempunyai nilai minimum 5.5.
step1-2: Dari atas ke bawah, tentukan nod bukan daun lapisan demi lapisan, yang merupakan perihalan aspek Nama [100] sebagai lapisan pertama, [10, 20, ?, ?] sebagai lapisan kedua dan sebagainya. pada. Mengikut keputusan langkah1-1, nilai minimum lapisan kedua ialah [10, 20, >60, >5.5]. keputusan ialah [10, 20, 62.25, 7.75]
step1-3: Sama seperti di atas, tentukan lapisan ketiga, hasilnya ialah [5.5, 4.5] [9.5, 5.25, 5.25] [60, 1.125, 1.125] [6.625] 1.125]
Kumpulan terakhir di sini lebih istimewa dan perlu dipertimbangkan Pada masa 7.75 diperuntukkan, sudah ada 5.5 di sudut kiri bawah, jadi nombor yang tersedia secara bebas dalam 7.75 ialah 7.75-5.5=2.25 kedua-dua belah, dan hasilnya ialah [6.625, 1.125]
step1-4: Lapisan terakhir percaya Tidak perlu bertele-tele, ini sebenarnya langkah 2, cuma bahagikan sama rata.

Answer 2

Saya baru membaca soalan ini dan mendapati ia sangat menarik. Kemudian saya memikirkannya dan bertanya soalan berikut.
Idea saya ialah rekursi.

1. Traverse secara hierarki, tambah nilai yang ditentukan pada setiap peringkat, dan bahagikan nod kosong ke dalam nilai nod induk tolak jumlah nilai yang ditentukan (keperluan soalan). Kemudian jika nod itu bukan nod daun, ulangi mengikut kaedah di atas.

2. Tetapi apabila menentukan nilai setiap nod, seperti nod daun tertentu, kita perlu memberikan nilai secara rawak kepada mereka Beberapa nilainya dikekang oleh nod induk, dan ada yang tidak dikekang oleh nod induk. , seperti nod ketiga pada lapisan kedua Dua nod daun , jika nilai yang kita berikan kepada mereka menjadikan nod induknya tidak memenuhi keperluan, ini tidak memenuhi maksud soalan. Jadi apa yang saya mahu ialah lulus dalam julat nilai nod ini setiap kali nilai ditentukan. Penentuan skop ini akan membawa kepada beberapa masalah, dan masalah akan menjadi rumit.

3. Julat ditentukan Nilai maksimum setiap nod kosong mestilah jumlah nilai nod induk tolak nilai nod anak yang sama . Oleh kerana hanya julat tertentu yang ditentukan, pemilihan beberapa nilai rawak nod daunnya tidak akan menyebabkan nod yang tinggal tidak memenuhi maksud soalan. Secara amnya, nilai setiap nod kosong dengan nod induk yang sama dikekang walaupun nilai satu nod memenuhi dirinya sendiri, ia akan menjadikan nod yang lain tidak memenuhi keperluan. Contohnya:
   

Jika nilai diambil dengan cara ini, ia akan berpuas hati secara tempatan, yang akan menyebabkan nilai nod lain tidak memenuhi keperluan. Oleh itu, ia boleh membawa kepada hasil yang tidak dijangka tanpa kekangan. Kita perlu menentukan julat ini.

Ringkasnya, ini hanyalah sebahagian daripada pemikiran saya selepas memikirkannya mungkin terdapat beberapa kesilapan dan sila betulkan saya.