Eksik basamakları bulmak
Verilen bir bölenin katı olan küçük sayıyı bulmakla ilgili bir URI sorusunu çözüyordum. Bu sorunu buldum:
Temettü: 4? 3? 771? 2? 166 ?? 56 ?? 357? 2223
Bölen: 909
Temettü ödememi doldurmam gerekiyor '?' sayılarla ve sabit sayıları değiştirmeden kalan = 0 ile sonuçlanan olası en düşük sayıyı bulun.
Python ile biraz kaba kuvvet denedim ama hızlı bir algoritma alamadım.
Bunu nasıl yapabilirim?
Yanıtlar
Bunun ilginç bir programlama alıştırması olduğunu düşündüm, bu yüzden bir şeyler yaptım. İşte bulduğum şey:
import math
import time
def fill_in(N,exps): #returns True,list if successful
n = 909
if exps:
ten_pow = 10**exps[0]
for a in range(10):
flag,coefs = fill_in(N + a*ten_pow,exps[1:])
if flag:
coefs.insert(0,a)
return (True,coefs)
return (False,[])
else:
return ((N%n == 0),[])
start_time = time.time()
N = 403077102016600560035702223
exps = [25,23,19,17,13,12,9,8,4]
flag,ans = fill_in(N,exps)
print("Answer:")
print(ans)
print("--- %s seconds ---" % (time.time() - start_time))
Çıktım:
Answer:
[0, 0, 4, 6, 9, 8, 9, 9, 9]
--- 2.5748291015625 seconds ---
Görünüşe göre cevap $$ 4\color{red}{0}3\color{red}{0}771\color{red}{4}2 \color{red}{6}166\color{red}{9}\color{red}{8}56 \color{red}{9}\color{red}{9}357\color{red}{9}2223. $$W | A ile, bu sayının gerçekten 909'a bölünebileceğini görüyoruz .
Bunların hepsini biraz daha uyarlanabilir hale getirmek için:
def fill_in_str(string):
exps = [i for i in range(len(string)) if string[-i-1] == '?'][::-1]
N_str = string.replace('?','0')
flag,ans = fill_in(int(N),exps)
if flag:
return string.replace('?','%d') % tuple(ans)
else:
return 'NONE'
string = '4?3?771?2?166??56??357?2223'
output = fill_in_str(string)
print("Answer: " + output)
Çıktı:
Answer: 403077142616698569935792223
Açıklama: İşlev fill_in(N,exps,n)bir sayı alır$N$, üslerin listesi $k_1,\dots,k_q$ azalan sırayla ve $n$ (bu durumda $n = 909$). Sayıları arar$a_1,\dots,a_q$ öyle ki $N + \sum_{i=1}^q a_i 10^{k_i}$ ile bölünebilir $909$. Bu tür sayılar bulursa, bir "True" bayrağı ve katsayıların listesini döndürür.$[a_1,\dots,a_q]$. Aksi takdirde, "False" ve boş bir liste döndürür.
İşlev yinelemeli olarak çalışır: için her değeri alır $a_1$ itibaren $a_1 = 0,\dots,9$ ve sonra katsayıları arar $a_2,\dots,a_q$ öyle ki $$ N + a_1 10^{k_1} + \sum_{i=2}^q a_i 10^{k_i} $$ ile bölünebilir $n$.
Yinelemenin alt kısmı, boş üsler listesi için oluşur: Doldurulacak katsayı kalmadıysa, o zaman sonuçta bulduğumuz sayının (tüm sayıları doldurarak) $a_i$) bir katıdır $n$.
Not: Değeri ne olursa olsun, modu test etmeyi denedim $9$ ve mod $101$ayrı ayrı "işleri daha hızlı hale getirmek" için. Zaman kazandırmaz.
Daha yavaş, ancak daha kısa ve anlaşılması daha kolay olan ilginç bir alternatif:
def fill_in_v2(string):
n = 909
fstr = string.replace('?','%s')
num_uk = string.count('?')
for i in range(10**(num_uk+1)):
istr = str(i).zfill(num_uk)
nstr = fstr % tuple(istr)
if int(nstr)%n == 0:
return nstr
return 'NONE'
start_time = time.time()
string = '4?3?771?2?166??56??357?2223'
output = fill_in_v2(string)
print("Answer: " + output)
print("--- %s seconds ---" % (time.time() - start_time))
Çıktı:
Answer: 403077142616698569935792223
--- 6.86776328086853 seconds ---
Bilinmeyen rakamları işleyin $a$ -e $i$soldan sağa. Bölünebilirlik testlerini kullanmayı deneyelim:
- Bölünebilirlik ölçütü $101$: Sağdan iki basamaklı blokların dönüşümlü toplamı $101$.
$-4+10a+3-10b-7+71-10c-2+10d+1-66+10e+f-56+10g+h-35+70+i-22+23\to 10(a-b-c+d+e+g)+(f+h+i)=101m+24$
Bilinmeyenlerin her biri için negatif olmayan tek basamaklı sol tarafın şundan büyük olamayacağını unutmayın: $387$ veya daha az $-180$. Bu güçler$m\in\{-2,-1,0,1,2,3\}$. Bunu daha sonra kullanmak üzere dosyaladık.
- Bölünebilirlik ölçütü $9$: Yukarıdakiyle aynı basamak çiftlerinin toplamı şuna bölünebilir:$9$. Bu garip görünüyor, ancak yakında bunu neden yaptığımızı göreceğiz.
$4+10a+3+10b+7+71+10c+2+10d+1+66+10e+f+56+10g+h+35+70+i+22+23\to 10(a+b+c+d+e+g)+(f+h+i)=9n$ (bilinen rakamlar iptal $\bmod 9$).
Buraya $n$ negatif olmayan bir tam sayıdır küçüktür veya eşittir $63$.
Şimdi ilk denklemi ikinciden çıkaralım, soldaki çoğu terimin iptal olmasına neden olalım:
$20(b+c)=9n-101m-24$
Şimdi, sağ tarafın negatif olmayan bir katı olmalıdır $20$, küçüktür veya eşittir $18×20=360$, ile $m$daha önce tanımlanan değerlerden birine sahip olmak. Her biri için tüm çözümleri belirleyerek onları deniyoruz$m$ bu tatmin edici $0\le b+c\le 18$ ve $0\le n\le63$:
$m=-2\to 20(b+c)=9n+178; n=18; b+c=17$
$m=-1\to 20(b+c)=9n+77; n\in\{7,27\}; b+c\in\{7,16\}$
$m=0\to 20(b+c)=9n-24; n\in\{16,36\}; b+c\in\{6,15\}$
$m=1\to 20(b+c)=9n-125; n\in\{25,45\}; b+c\in\{5,14\}$
$m=2\to 20(b+c)=9n-226; n\in\{34,54\}; b+c\in\{4,13\}$
$m=3\to 20(b+c)=9n-327; n\in\{43,63\}; b+c\in\{3,12\}$
Minimal çözümü arıyoruz, bu yüzden $b+c=3$ ile $b=0,c=3$, sağ? Bunu gerçekleştiriyoruz. İle$b+c=3$ sahibiz $m=3,n=43$ ve dolayısıyla toplam $10(a+b+c+d+e+g)+(f+h+i)$ bölünebilirlik testimizden elde edilen $9$ olacak $387$. Sonra$f+h+i$ bitmeli $7$ve daha yüksek değerli rakamları en aza indirmek için bu toplamı mümkün olduğu kadar büyük yapmalıyız. Bu nedenle$f,h,i$ hepsi $9$. Bu birlikte$b=0,c=3$ yapraklar $(387-30-27)/10=33$ kalan dört hanenin toplamı için ve seçtiğimiz toplam sayıyı en aza indirmek için $a=6,d=e=g=9$.
Ortaya çıkan sayı şu şekilde bölünebilir: $909$, ancak nispeten yüksek bir rakamı var $a$ basamak değeri kimin $b$ veya $c$. Yani belki daha yüksek bir değer$b+c$ daha düşük bir değer verebilir $a$. Alabilir miyiz$a$ aşağı $0$ve en küçük artış nedir $b+c$, ve bu nedenle $c$ ile $b=0$, bunu yapmamız mı gerekiyor?
İçin $b+c=4,b=0,c=4$ sahibiz $m=2,n=34$. Bizim toplam$9$-bölümlenebilirlik testi şimdi $306$, ile biten $6$. Bu nedenle$f+h+i$aynı şeyi takip etmelidir. Bu toplamı tekrar maksimize ediyoruz ve iki farklı değer bularak daha küçük olanı seçiyoruz$f$. Böylece$f=8,h=i=9$. Kalan basamaklar$a,d,e,g$ şimdi toplanacak $(306-40-26)/10=24$. Bu yana bu daha az olan ya da eşit daha$27$ayarlayabiliriz $a=0$ ve toplamını paylaştırın $24$ arasında $d,e,g$. Dolayısıyla, mümkün olan en küçük değere sahip minimum çözüm$a$ ve gereksiz yere büyük değerler değil $b,c$ veya $d$, tarafından işlenir
$a=b=0, c=4, d=6, e=9, f=8, g=h=i=9.$
$N=403077142616698569935792223.$
Modulo $909$yer değerleri (güçleri $10$) döngüyü takip edin $\overline{1,10,100,91}$. Basamak değerleriyle bilinmeyenler yok$\equiv100$, ancak diğer üç kalıntı için bilinmeyen rakamlar için ayrı artan diziler görüyoruz:
$\equiv1: f\le h\le i$
$\equiv10: a\le d\le e\le g$
$\equiv91: b\le c$
'?' ile noktalar$0$bizi tanımlamaya götürür $N$ ve hesapla
$\quad N = 403077102016600560035702223 \equiv 279 \pmod{909}$
Not: OP'nin başlangıç numarası, soru işaretleriyle birlikte sıfır olmayan tüm rakamlara sahipti, bu nedenle içindeki tüm sıfırlar $N$ ikamesine açıktır.
Biz de var $k \in \{1,2,3,4,5,6,7,8,9\}$,
$\quad k * 10^0 \equiv k\pmod{909}$
$\quad k * 10^1 \equiv k * 10^1 \pmod{909}$
$\quad k * 10^2 \equiv k * 10^2 \pmod{909}$
$\quad k * 10^3 \equiv k * 91 \pmod{909}$
$\quad k * 10^4 \equiv k \pmod{909}$
Şimdi beri $279 + 630 \equiv 0 \pmod{909}$, biz 'çalışabiliriz' $630$ yazarak açık
$\quad N + 6 * 10^3 + 8 *10 + 4 \equiv 0 \pmod{909}$
Bir 'bulmak için döngüsel kaydırma mantığını kullanmak? \$0$' yer,
$\quad N + 6 * 10^3 + 8 *10 + 4 =$
$\quad \quad 403077102016600560035702223 + 6 * 10^3 + 8 *10 + 4 \equiv$
$\quad \quad 4030771\color{red}{6}2016600560035702223 + 8 *10 + 4 \equiv$
$\quad \quad 4030771\color{red}{6}201660056\color{red}{8}035702223 + 4 \equiv$
$\quad \quad 4030771\color{red}{6}201660056\color{red}{8}0357\color{red}{4}2223 \equiv 0 \pmod{909}$
Bu yüzden bir çözüm bulduk ve şimdi onu en aza indirmek istiyoruz. Ondalık genişletme noktalarının
$\quad 10^2, 10^6, 10^{10}, 10^{14}, 10^{18}, 10^{22}, 10^{26}$
numara için $N$değil mi? \$0$'noktalar; bu, OP'nin problemi için basitleştirici bir kısıtlamadır.
Alıştırma: Minimum çözümü bulun $\;\,4?3?771?2?166??56??357?2223 \equiv 0 \pmod{909}$.
İpucu: için hiçbir çözüm olmadığını gösterin.$4\color{red}{0}3\color{red}{0}771\color{red}{3}2?166??56??357?2223 \equiv 0 \pmod{909}$ beraberinde bazı çözüm mantığı ile.