Soalan ProjectEuler 17: Saya menukar baris kod ini dan jawapan saya berubah secara dramatik, walaupun saya fikir ia sepatutnya berfungsi

editor php Apple menghadapi situasi yang menarik dalam ProjectEuler isu 17. Selepas dia menukar satu baris kod, dia mendapati jawapannya berubah secara mendadak, walaupun dia fikir kod itu harus berfungsi dengan betul. Soalan ini menimbulkan rasa ingin tahunya, dan dia mula meneroka sebab-sebabnya dan mencari penyelesaian. Kisah ini penuh dengan cabaran dan pemikiran, membuatkan orang ramai menantikan jawapan editor.

Kandungan soalan

Saya sedang mengusahakan projek euler soalan 17. Saya harus menulis program untuk mengira jumlah bilangan aksara dalam nombor bertulis 1-1000. Anda mengabaikan ruang dan sempang. Menurut huraian masalah, beratus-ratus nombor termasuk "dan" (tiga ratus empat puluh dua). Kod saya berfungsi dalam kebanyakan kes kecuali gandaan 100 (apabila ia mengira "jumlah" tambahan). Sebagai contoh, kira 600 sebagai "enam ratus dan." Ini menyebabkan jawapan saya menyimpang daripada 27 (3 daripada 100 digit). Ini hampir penyelesaian yang betul:

string[] nums = {"",
                 "one",
                 "two",
                 "three",
                 "four",
                 "five",
                 "six",
                 "seven",
                 "eight",
                 "nine",
                 "ten",
                 "eleven",
                 "twelve",
                 "thirteen",
                 "fourteen",
                 "fifteen",
                 "sixteen",
                 "seventeen",
                 "eighteen",
                  "nineteen"};
string[] ten = {"",
                "",
                "twenty",
                "thirty",
                "forty",
                "fifty",
                "sixty",
                "seventy",
                "eighty",
                "ninety"};
int sum = 0;
map<integer, integer> ones = new hashmap<>();
map<integer, integer> teens = new hashmap<>();
map<integer, integer> tens = new hashmap<>();
for (int i = 0; i < 10; i++) {
    ones.put(i, nums[i].length());
}
for (int i = 10; i < nums.length; i++) {
    teens.put(i, nums[i].length());
}
for (int i = 0; i < ten.length; i++) {
    tens.put(i * 10, ten[i].length());
}
for (int i = 1; i < 1000; i++) {
    int num = 0;
    int n = i % 100;
    if (n > 19 || n < 10) {
        num += ones.get(n % 10);
        num += tens.get(n - n % 10);
    }
    else {
        num += teens.get(n);
    }
    num += i > 99 ? "hundredand".length() : 0;
    num += ones.get(i / 100);
    system.out.println(num + " " + i);
    sum += num;
}
sum += ("onethousand").length();
// actual is 21124
system.out.println(sum);

Ini menghasilkan output 21151, iaitu 27 berbeza daripada output jangkaan 21124. Pembolehubah num digunakan untuk tujuan nyahpepijat.

Saya cuba menukar salah satu baris gelung dan menambah pernyataan tambahan:

num += i>99 ? "hundred".length() : 0;
num += i%100==0 ? 3 : 0;

Selepas menjalankan versi yang dikemas kini ini, outputnya ialah 18487. Saya tidak pasti mengapa perbezaan ini begitu ketara dan ingin memahami dari mana asalnya. Saya mula-mula fikir ia adalah kerana pengendali ternary, kerana pengetahuan saya tentangnya adalah terhad. Selain itu, sebarang cadangan untuk menjadikan kod lebih cekap adalah dialu-alukan. Saya ingin memasukkan sum-27 sebelum mencetak, tetapi saya rasa itu agak menipu :). Terima kasih!

Penyelesaian

Seperti yang orang lain katakan dalam ulasan kepada soalan anda, masalah anda ialah bagaimana kod anda mengendalikan nombor yang berganda 100. Anda sentiasa menambah seratus dan jangan sekali-kali hanya seratusum>. Malah, anda menyatakan diri anda dalam soalan anda:

Dalam kod di bawah, saya menggunakan pernyataan if eksplisit - bukannya pengendali ternari - kerana saya percaya ia menjadikan kod lebih mudah difahami semasa membaca. Sila ambil perhatian bahawa ini adalah satu-satunya perubahan yang saya buat pada kod yang disiarkan dalam soalan anda.

import java.util.hashmap;
import java.util.map;

public class myclass {
    public static void main(string args[]) {
        string[] nums = {"",
                         "one",
                         "two",
                         "three",
                         "four",
                         "five",
                         "six",
                         "seven",
                         "eight",
                         "nine",
                         "ten",
                         "eleven",
                         "twelve",
                         "thirteen",
                         "fourteen",
                         "fifteen",
                         "sixteen",
                         "seventeen",
                         "eighteen",
                         "nineteen"};
        string[] ten = {"",
                        "",
                        "twenty",
                        "thirty",
                        "forty",
                        "fifty",
                        "sixty",
                        "seventy",
                        "eighty",
                        "ninety"};
        int sum = 0;
        map<integer, integer> ones = new hashmap<>();
        map<integer, integer> teens = new hashmap<>();
        map<integer, integer> tens = new hashmap<>();
        for (int i = 0; i < 10; i++) {
            ones.put(i, nums[i].length());
        }
        for (int i = 10; i < nums.length; i++) {
            teens.put(i, nums[i].length());
        }
        for (int i = 0; i < ten.length; i++) {
            tens.put(i * 10, ten[i].length());
        }
        for (int i = 1; i < 1000; i++) {
            int num = 0;
            int n = i % 100;
            if (n > 19 || n < 10) {
                num += ones.get(n % 10);
                num += tens.get(n - n % 10);
            }
            else {
                num += teens.get(n);
            }
            if (i > 99) {
                num += n == 0 ? "hundred".length() : "hundredand".length();
            }
            num += ones.get(i / 100);
            sum += num;
//            system.out.printf("%2d %3d %5d%n", num, i, sum);
        }
        sum += ("onethousand").length();
        // actual is 21124
        system.out.println(sum);
    }
}

Apabila saya menjalankan kod di atas, saya mendapat keputusan berikut:

21124

Dalam kod soalan anda, anda menulis (dalam komen kod) bahawa ini adalah jawapan yang diharapkan.

Atas ialah kandungan terperinci Soalan ProjectEuler 17: Saya menukar baris kod ini dan jawapan saya berubah secara dramatik, walaupun saya fikir ia sepatutnya berfungsi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!