Müfredat 148 dersinden 134. · Kendi rekorunu kır
Kendi rekorunu kır

Önbellek yok: miras alınan indirimler

Neden önemli "İşi tekrar eder, bu yüzden cevapları hatırla" programlamada, ister insan ister yapay zeka olsun, en güçlü alışkanlıklardan biridir. Bazen işin hiç tekrar edilmesine gerek kalmaz.

A mağazasının kategorileri bir ağaç oluşturur: Bahçe Evin altında, Aletler Bahçenin altında ve bu şekilde devam eder. Bir pazarlama yöneticisi herhangi bir kategoriye indirim tanımlayabilir ve bu indirim, daha yakın bir kategori kendi indirimini tanımlamadığı sürece altındakilerin tamamına uygulanır. Ödeme ekranı binlerce kategori için geçerli indirimi aynı anda kontrol eder.

Veri

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

Ağaç üzerinde tekrarlanan yürüyüşler için bariz çözüm bir cache kullanmaktır. Bu problemde cache yasak. En baştan işi asla tekrar etmeyecek bir yol bul.

Senin sıran

effective_discounts(parents, own, queries) yaz. parents her kategoriyi üst kategorisine, veya en üst seviye bir kategori için None'ye eşler (birkaç tane olabilir ve sözlük belirli bir sırada değildir). own bazı kategorileri kendi indirimlerine eşler. queries içindeki her kategori için, kendisiyle başlayarak yukarı doğru giden yol üzerindeki, own içinde indirimi olan en yakın kategorinin indirimini döndür; hiçbiri yoksa 0 döndür. Kuralı: önbellek veya memo yok: functools önbellek dekoratörleri yok, "cache" veya "memo" içeren isimler yok ve sorgular istediği için onları dışarı aktarıp tutmak yok (başka isimle bir memo). Önce tüm ağacı gez, sonra sorguları oku. Bütçe: 3.000 kategori, birkaç yüz seviye derinliğe kadar ağaçlar ve 20.000 arama için en fazla 500.000 adım (steps()).

Bu derste bir sorun mu fark ettin? Bildir · Bu ders hakkında soru sor

Bu alıştırma yakında açılacak

Bu dersi bitirince bu ders açılacak. Kursun tamamı ücretsiz, hesap gerekmiyor ve bu dersi hemen şimdi okuyabilirsin.