Memecahkan persamaan dengan pembagian integer tanpa kekuatan kasar

Baru-baru ini, sebuah pertanyaan muncul di Toaster , yang sangat menyentuh saya. Ini berakar pada tugas yang akan saya berikan di sini dalam interpretasi yang sedikit berbeda:

Setelah programmer lulus proyek tepat waktu dan menerima hadiah. Untuk merayakannya, mereka melemparkan diri ke Mon dan membeli bir dengan semua uang. Mereka minum semuanya pada hari yang sama, dan di BT memutuskan untuk melanjutkan, tetapi tidak ada lagi uang yang tersisa. Kemudian mereka menyerahkan botol-botol itu, menambahkan uang receh kemarin, dan sekali lagi mereka menyimpan semuanya, seperti kemarin. Hal yang sama dilakukan di SR dan Chet. Dan di PT uang hanya satu botol. Pikir - ingat harga satu botol, berapa banyak mereka mengambil wadah (harga tanpa sen), dan tidak ada yang bisa menyebutkan berapa banyak uang yang awalnya. Proyek ini berskala besar, bonus besar - jadi tidak sepadan. Berapa anggaran minimum di PN sehingga acara akan berkembang dengan cara ini?

Alasannya sebagai berikut


Saya sampai pada persamaan yang secara abstrak terlihat seperti ini (1):

$$

$$x = a (x // b) + c$$

Mencoba menemukan pendekatan tanpa pencarian lengkap untuk menyelesaikan persamaan seperti itu, saya menghabiskan lebih dari satu jam, tetapi pada akhirnya saya menemukan solusi yang benar-benar luar biasa , tetapi margin buku ini terlalu sempit ;)

Tanpa ilusi tentang keunggulan dalam hal ini, saya hanya ingin berbagi kesenangan yang diterima dalam proses ini. Jika ada yang tahu metode atau nama alternatif untuk ini, beri tahu saya; Saya mendesak mereka seperti saya untuk berdiskusi, dan yang tidak sabar, saya mengundang Anda di bawah kucing.

Pertimbangkan persamaan yang dihasilkan dalam formulir ini (2):

$$

$$(x-c) / a = x // b$$

karena sisi kanan hanya dapat mengambil nilai integer, seluruh ekspresi hanya masuk akal ketika pembilangnya adalah kelipatan dari penyebut di sisi kiri. Dari sini jelas bahwa x dapat memiliki nilai mulai dari c dan kemudian dengan langkah a .

Kemudian saya menganggap persamaan (1) sebagai dua fungsi $$$y1 = x$dan $$$y2 = a (x // b) + c$. Pada argumen apa mereka berpotongan, itulah solusinya. Sebagai contoh, saya memilih nilai kecil dari parameter sedemikian rupa untuk menampilkan gambar sebaik mungkin. Jadi, biarkan a = 3, b = 7, c = 9.


Karena sifat bertahap dari fungsi kedua, grafik y1 dan y2 berpotongan pada dua titik: untuk x1 = 12 dan x2 = 15, tetapi menurut kondisi ini, kami tertarik pada nilai pertama, sebagai yang lebih kecil. Jadi, untuk menentukan area persimpangan tanpa pencarian lengkap, saya memperkenalkan fungsi ketiga - itu hanya garis lurus yang membatasi fungsi y2 dari bawah dan memiliki persamaan $$$y3 = a / b (x - (b-1)) + c$.

Sekarang tinggal mencari titik persimpangan dari dua garis ( y1 dan y3 ) dan sesuaikan jawaban dari batasan pada x yang diinginkan. Memang, berdasarkan kondisi, hanya dapat mengambil nilai-nilai di mana kondisi pengganda pembilang puas untuk penyebut dalam persamaan (2), yaitu $$$x = c + na$, di mana n adalah faktor alami tertentu. Untuk melakukan ini, kami memecahkan persamaan sederhana $$$x = a / b (x - (b-1)) + c$dan jika root yang dihasilkan tidak memenuhi persyaratan kami, kami akan memindahkannya ke yang cocok terdekat. Karena fungsi bantu y3 memiliki kemiringan positif, dan semua nilai y2 berada di atasnya, root harus selalu disesuaikan ke atas. Jadi, dalam kasus kami, garis berpotongan di x = 11,25 (titik hitam pada grafik), dan nilai besar terdekat yang memenuhi syarat adalah 12 (titik merah), yang merupakan jawabannya.

Karena ada tag Python dalam pertanyaan tentang Pemanggang Roti, di bawah ini saya akan memberikan skrip untuk memecahkan masalah ini menggunakan fungsi, untuk menemukan anggaran hari ini berdasarkan anggaran hari berikutnya. Kami menerapkan fungsi beberapa kali dan, voila, kami mendapatkan jawabannya!

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) 

Alih-alih kesimpulan:

tugas dalam contoh ini ditentukan sebagai nilai parameter $$$a <b <c <x$, dan persamaan itu sendiri $$$x = a (x // b) + c$; pendekatan yang diusulkan dengan perubahan kecil dapat diterapkan dalam kasus serupa lainnya - tujuan publikasi hanya untuk menggambarkan prinsip tanpa menurunkan solusi universal untuk kasus umum - oleh karena itu, jangan menilai secara ketat (kode Python, termasuk), dan selamat menikmati Jumat!