Kos minimum untuk menukar 1 kepada N, yang boleh dicapai dengan mendarab dengan X atau putaran kanan nombor

Kita boleh menggunakan teknik berikut untuk mencari cara termurah untuk mendarab X atau memutarkan nombornya dari 1 ke N. Untuk memantau kos minimum awal, buat pembolehubah kos. Apabila pergi dari N ke 1, semak sama ada N boleh dibahagi dengan X pada setiap peringkat. Jika ya, kemas kini dengan membahagikan N dengan X dan teruskan proses. Jika N tidak boleh dibahagikan dengan X, maka gelungkan digit N ke kanan untuk meningkatkan nilainya. Tambahkan pembolehubah kos dalam kes ini. Nilai pembolehubah kos akhir ialah jumlah minimum yang diperlukan untuk menukar 1 kepada N. Algoritma dengan cekap menentukan operasi minimum yang diperlukan untuk melakukan transformasi yang diingini menggunakan putaran atau pendaraban berangka.

Kaedah penggunaan

• Pendekatan Naif: Putaran nombor yang betul

• Kaedah yang cekap: darab dengan X

Cara mudah: nombor putar ke kanan

Pendekatan naif adalah bermula dengan nombor 1 dan berulang kali putarkan nombornya ke kanan sehingga anda mencapai nombor sasaran N. Pada setiap putaran, nombor terakhir bertukar kepada nombor pertama. Walaupun secara konsepnya mudah, strategi ini boleh menjadi tidak cekap untuk nilai N yang besar dan mungkin memerlukan banyak langkah untuk mencapai nombor sasaran. Apabila N meningkat, bilangan putaran juga meningkat dengan cepat, menjadikannya kaedah yang kurang berkesan untuk menentukan kos minimum untuk menukar 1 kepada N. Oleh kerana ketidakcekapannya, kaedah ini tidak disyorkan untuk nilai N yang besar, manakala kaedah lain, seperti membahagikan N dengan X, telah terbukti lebih cekap dalam mencari kos transformasi yang paling rendah.

Algoritma

• Buat "kos" pembolehubah untuk menjejaki langkah yang diperlukan untuk mencapai N dan mulakannya kepada 1 untuk mewakili nilai semasa.

• Ulang arahan ini sehingga nombor semasa sama dengan N:

  Putar digit nombor semasa ke kanan supaya digit terakhir menjadi digit pertama.

  Rekodkan bilangan putaran yang diperlukan dengan menambah pembolehubah "kos" sebanyak 1.

• Setelah nombor semasa bersamaan dengan N, pembolehubah "kos" akan menyimpan bilangan langkah minimum yang diperlukan untuk memutarkan integer asal (1) kepada N menggunakan putaran kanan.

Contoh

#include <iostream>
#include <cmath>

int rotateDigits(int num, int numDigits) {
    return (num / 10) + (num % 10) * std::pow(10, numDigits - 1);
}

int main() {
    int N = 123; // Replace this with your desired N value

    int current = 1;
    int cost = 0;
    bool found = false;

    while (current != N) {
        int numDigits = std::to_string(current).length();
        current = rotateDigits(current, numDigits);
        cost++;

        if (cost > N) {
            std::cout << "N cannot be reached from 1 using right rotations." << std::endl;
            found = true;
            break;
        }
    }

    if (!found) {
        std::cout << "Minimum steps to reach N: " << cost << std::endl;
    }
    return 0;
}

Output

N cannot be reached from 1 using right rotations.

Kaedah yang cekap: darab dengan X

Cara terbaik untuk meminimumkan kos pendaraban 1 dengan N adalah dengan membahagikan N dengan X secara berkala sehingga hasilnya ialah 1. Untuk mencapai matlamat ini, mulakan pembolehubah kos untuk memantau kos minimum. Kami menentukan sama ada N boleh dibahagikan dengan X dengan bermula dengan nilai N. Jika kedua-dua N dan X boleh dibahagikan, kos meningkat dan operasi pembahagian dilakukan. Ulangi proses ini sehingga N sama dengan 1. Kaedah ini lebih cekap daripada "putaran nombor kanan" kerana ia memerlukan lebih sedikit langkah untuk mendapatkan hasil 1. Oleh kerana sifatnya yang lebih cepat dan lebih cekap, ia adalah kaedah pilihan untuk menentukan kos pensuisan terendah.

Algoritma

• Untuk menjejaki kos minimum, mulakan "kos" pembolehubah kepada 0.

• Mulakan dari nombor sasaran yang diberikan N, menggunakan pengganda tetap X.

• Selagi N lebih besar daripada 1, ulangi langkah 4 hingga 6.

• Dengan mengandaikan N% X == 0, tentukan sama ada N boleh dibahagi dengan X.

• Jika N boleh dibahagi (N = N / X), bahagikan N dengan X dan tambah 1 pada pembolehubah "kos".

• Jika tidak boleh dibahagikan, gelungkan nombor N ke kanan (dengan menggerakkan digit terakhir ke angka pertama) dan naikkan "kos" sebanyak 1.

• Ulang langkah 3 hingga 6 sehingga N menjadi 1.

• "Kos" terakhir mewakili minimum yang diperlukan untuk mendarab dengan X atau mengalihkan nombor ke kanan untuk menukar 1 kepada N.

Contoh

#include <iostream>
#include <cmath>

int main() {
    int X = 3;
    int N = 100;
    int cost = 0;

    while (N > 1) {
        if (N % X == 0) {
            N /= X;
            cost++;
        } else {
            int lastDigit = N % 10;
            N = (N / 10) + (lastDigit * std::pow(10, std::floor(std::log10(N))));
            cost++;
        }
    }

    std::cout << "Final cost: " << cost << std::endl;

    return 0;
}

Output

Final cost: 2

Kesimpulan

Ringkasnya, apabila ia datang untuk menentukan kos terendah untuk menukar 1 kepada N dengan mendarab dengan X atau memusingkan nombor ke kanan, kaedah yang cekap untuk mendarab dengan Pendekatan yang lebih diperkemas yang disediakan oleh kaedah yang cekap memerlukan lebih sedikit langkah untuk mencapai bilangan N yang diperlukan. Sebaliknya, kaedah naif boleh menjadi tidak berkesan dan memakan masa, terutamanya untuk nilai N yang lebih tinggi. Kita boleh mengurangkan proses yang diperlukan dan menggunakan kaedah yang cekap untuk menentukan cara paling menjimatkan untuk menukar 1 kepada N. Strategi ini menyelesaikan masalah menentukan kos minimum proses penukaran ini dan terbukti sebagai algoritma yang lebih berguna dan cekap.

Atas ialah kandungan terperinci Kos minimum untuk menukar 1 kepada N, yang boleh dicapai dengan mendarab dengan X atau putaran kanan nombor. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!