Exercices - algorithmes gloutons

Exercice 1 : conversion gloutonne

Pour convertir en base \(2\) un entier écrit en base \(10\), nous pouvons utiliser l'algorithme glouton de rendu de monnaie, en utilisant les puissances de \(2\) successives comme valeurs des pièces.

Par exemple, pour obtenir la représentation binaire de \(43\), on peut utiliser les valeurs \(32\), \(16\), \(8\), \(4\), \(2\) et \(1\). On se limite à \(32\) car la puissance suivante, \(64\), est strictement supérieure à \(43\).

On procède alors ainsi :

• Pour \(43\) on doit prendre \(32\) , il reste \(11\),
• Pour \(11\) on ne peut pas prendre \(16\) (en effet \(16>11\)),
• Pour \(11\) on doit prendre \(8\), il reste \(3\),
• Pour \(3\) on ne peut pas prendre \(4\),
• Pour \(3\) on doit prendre \(2\), il reste \(1\),
• Pour \(1\) on doit prendre \(1\), il reste \(0\).

On obtient la représentation binaire en observant les différentes étapes : s'il est possible de prendre une puissance, on note un 1, si c'est impossible, on note un 0.

Puissance de 2	Possible ?	Bit correspondant
\(32\)	Oui	1
\(16\)	Non	0
\(8\)	Oui	1
\(4\)	Non	0
\(2\)	Oui	1
\(1\)	Oui	1

Dans la pratique, pour convertir « à la main » \(43\) en binaire, cela revient réaliser le tableau suivant :

\(32\)	\(16\)	\(8\)	\(4\)	\(2\)	\(1\)
1	0	1	0	1	1

On en déduit que \(43\) en décimal s'écrit 101011 en binaire.

✏️ À vous de jouer ... sur papier

Utiliser la méthode précédente pour convertir 100 en binaire.

Solution

on peut utiliser les valeurs \(64\), \(32\), \(16\), \(8\), \(4\), \(2\) et \(1\). On se limite à \(64\) car la puissance suivante, \(128\), est strictement supérieure à \(100\).

On procède alors ainsi :

• Pour \(100\) on doit prendre \(64\) , il reste \(36\),
• Pour \(36\) on doit prendre \(32\), il reste \(4\)
• Pour \(4\) on doit prendre \(4\), il reste \(0\)

On obtient la représentation binaire en observant les différentes étapes : s'il est possible de prendre une puissance, on note un 1, si c'est impossible, on note un 0.

Puissance de 2	Possible ?	Bit correspondant
\(64\)	Oui	1
\(32\)	Oui	1
\(16\)	Non	0
\(8\)	Non	0
\(4\)	Oui	1
\(2\)	Non	0
\(1\)	Non	0

Dans la pratique, pour convertir « à la main » \(100\) en binaire, cela revient réaliser le tableau suivant :

\(64\)	\(32\)	\(16\)	\(8\)	\(4\)	\(2\)	\(1\)
1	1	0	0	1	0	0

On en déduit que \(100\) en décimal s'écrit 1100100 en binaire.

Travail à faire

Vous devez écrire une fonction binaire qui prend en paramètre un entier écrit en base \(10\), et renvoie la chaîne de caractères la plus courte possible (sans zéros inutiles) représentant sa conversion en binaire.

Exemples

🐍 Console Python

>>> binaire(43)
'101011'
>>> binaire(32)
'100000'
>>> binaire(0)
'0'
>>> binaire(54321)
'1101010000110001'

Contraintes

Vous utiliserez obligatoirement un algorithme glouton qui met en oeuvre la méthode décrite dans cet exercice.
L'utilisation de la fonction bin et du modulo (%) est interdite.

Compléter le script ci-dessous

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)

Entrer ou sortir du mode "plein écran"
(Esc)

Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)

Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Évaluations restantes : 5/5

.128073.128013è5_1Dy):u(gnm]=wvqi,txb9à0372orsRa.+4/[EVlpCS Ahe*éz-cf8dPk6;050*0Y0w0J0u0R0H0V0%0R0J0H0H0q010w0u0S010406050H0k0o0o0J0G0h040U0F0R0k120F0n0V020J0o0S0.0V0I0Y1c0G0t0k0Y0H050N191b1d1f170S04051K1D1N0N1K170*0u0s0`0|0~100|0n0m0k0J0m0Y0$0S0h0w0X1m0V0X0u0m0X0R1?0X0w15050=0y0R0Y1W0}0 011=1@1_1@0w1 211}0w0G1L1.0`1i0H0S0J0n100E01231Y010(0@0Y0n1q0Y1}2l2n2s252v212y0o2A040b0V0+0G0F0S0F0H0u1l1n0:2j0G0G0Y0%2V1D2C0n1L0N1.2+2f2h2g1~0*2E1Z0u0n2x2S1}1T1V0{242^2`0n0F2~1}0S2!1L2)2+3b182m1n302t340G1c0R1}0J1;2!0(10030e0e0%350Y1_330F0$0f3C150V0f1D0J3c3f163e2D3h253j3l3n3p0Y3r013t3v3x3z2{3C0$2q040V0E3I3K2n3M2)2@013R0J3m1L3o0X3q3s3u3w0:3#343%0C3F0C3-2(3L173;3P103@3_053{3}3X3 3!2_3$3D0M3F0M481E4a3N3g1X3Q0F3k3^3T3|3V3~3Z414n433D0d3F0d4t3b4b3f3=4f4D4j3Y403y4J3B3D0-3F0-4P4v4c4y4e4A3S3`3U3W4X4m3A3%0D3F0D4*3/4R3O4-3?4/4C4;4E4?4l4I4_3D0)3F0)4~2*504x31534B4g4i4F4k4H4Z5b0$0z3F0z5g3:4S4d5l4:4h4=4G4Y424#3C0B150f0B5y5i4T545n5F5q5H4!3%0f0f5M3H0N3J494 4w5R5m4V5p4@5a4o3C3)0f3,5%3.5h5+5B4U564W595s5=0f4504655P5}525 5E575G4^644q674s5`5)5|4,5k6c5o585r5I5Y4M674O6l4u5*6o3i5S5.6s5W5t0f4%674)6z4Q6a6p6E605/626u3D0f4{674}6N4+5A6b6R6d616t5X6W5d675f6#6B6%6Q5-6S6G6g4K3C5v675x6=6n6@6D6_6*6T6,5t0E5L047b5y1O391D2~2.0*2h2?5B4Y2}1U1L380Y3a3L6m1L4Y7v2D0u0*103u2)5Y3T7C7E79642r2I0Y7K6H7M2+5(6C250,150:0(7x6P2t0r3F7#7V4e0(150y2_0?2!7*742514040l7?516p15340o0y7=6A2*7$7^150i0j7x17847A1n7J017F3f3%3)5E8g6U6-3(7N2z7Q6|5J8l5`0V8y0V86107X040u7!8d8A7+3?7 0F81833b8I7@100F150q0q7x8Q7}2t0o0u155O8d8B017_8a8d8c3d3;8n0e7G3D668m7D8h7L6}450V7O8t5;8~1}8x8z978*8D2!0w0k0G0n8X8*0H3)015L8b7|8f8{8i2n3%6i8`92636}4q908s8|7R9x953J8/7w8;9p8?8j4L7I9J9C5J4M9z2J9v6V0$6w3-988J0n150S0k0u0~2n0%1B0e1k2w1C8H8*8T048W9=8J7_0O0p9m8)9I7K8@0$6K9u9B8u3%4%9S7Pa7935Ja5968y8*9#040S9g8J9@9_8P8*8#5M9 8:4S8=a36Ya68o5t4{ab9U8paAah8Y5j2t8D0r1=21an8R8KalaR8Z259@020R0w0.aq3LaK4T8L8N0YaVaL87048-6Oa0ax9Ja36/aB8}5J5daFad9wa~9E3*978zaj9$9(9*0n9,0H9.12219;awaW8S150K9na*040J0S0S2x0*bo5B7_7{a@bkaTambAa/107_0iav9Ha^a29L5u9NaG5t5vb0aC5=6 9Yb6ai9!9$a.3=apb$5Bat7db)529@0Zb-7~aU8.boaybN5NbPb19Vb{bTa}5Y7cbXbZaSak9%9)0H9+0Y0e1c0xb;2tb(9`c60y152Hbw52bycob=c8bbbdbf9:cr2tbHcgaX150$cB10b+5$a?bj9obM9r6W5!4;8=9P5Y5!c0cScOb49G3/5+b_cN5?b|bU6}5^8r9Tb}8pc,7Tb5c5bBak2!19a!0J0wcF01ciar8J9i1501018XbY8zcZ85a18|a365c)c16W8 91c/6I8_aJ99150(4Ac ak0uc 0F7(8E9fcjc^cl040G2n1)cya:bzcKbpctcabccccedJbG150vdxcDdT01cHdZ7_dWdCbFd0dYbE3=d#d-bx88a=4vd-c$0n5Y9t3ocRa86W9ydlc*5J0f9taJ9Zc6b9c9cbdX9^dueacu9-9/bhd$150OdZdvel049~b@d^a_b`9Xd}9Od 3C9Re2dieBb4d9a)5B8D8Fef048082a-d)b%15020ma#a%3/eI6begdP9,eqd?5*eucMd`6Wa5eybQ64aaeDcW3Cag3JeHe8c^15c`0kc|c~eR5Bd1a(b8dF1Bf10=f3d2aS9@0Lc d404015!bJc!dd9qe-3CaAe:dm64aEe@eA6XeGe|c@d*akeO8Of7ao8UeMfGeQfebB9@cEf4e!albae$fNd@dMd_5Ya{fue3f#c-acf(6.fBbYdq043y0HfXfoaS8,fndcbLdeb`bWf%eE0fbSfyae5YbWe7d9f8f0f2edeX2*eZb=gcfcedfhfS5kfj9kd7etfZevc%7bdhe^gwcVeAgwc=e}d*9a0;9ddBfOfEe fagdgs7w0N7z7g7u7i7r1D0w7lgX2;2,0J20gU0N7j1J8e3=2!0o0e0(0J0,cc0X661v1x1z1B0Ve)851Q3M1K0a0V0T0;0V3^0m4A2U0X2J0V0m0R0F1k1:0n0!bd2T0w222X3w1b2x9,0G0V2mhxbhhy1j0_0mdG0n0:0_dOcb0_2X0E0Vej1Bbn820V0N160g2n0_0|0V0H1i9/1:382Q2S0!0Y0v90hj0_0J0s1m0_0%0G0!0!hP2`0V1_0Hhq0VhIhyfVhLi422hO2f0uh-hJ1d0V4A0*2!0`2Peb0n0w0Vg}h:0kh=h@0nif0G3w9d1A0V0Ahy1d12hx2Xh!2v0nbnh2g,h50W1kik2R0~0u7/1_0wh}2xhPbg9)2nip057z2RbDgSiN0/1U3=1!1$1(1*1,1.1:271^1`1|g-5B2G2x2z152M0Uh`13ip0+1-1/gJ7w7t8e5{7y3xg-f!0E3EcQezg6jocUg5b23(3E5U5:jwjtb4f:7ZdZdz8Ad:6b7-047/2y0ufHf^bBcqjJb=fMeq89f{jmgud`jo8lg1cSj%f*e;43j+jzf(j+gDb78JeK8GgKbpjWgnch8Ugf3*as8$048(dMd;a;jZc#j#jx8_j)a8jodk9Aj;0$8 6e5Vkgklf.b6f:9bgIfi9j9lgPjRcLf~9rjod|0Vd~js0$e1kjc1kE2rknjA6ukNc=dbj!e,jxexkGjrjB9Wj,fvj.k$j:kMk$j?fDdNi7dQbehQbifIfffKj~a:9}kafp9KkDa4gxkpe?kLj*l3k+l8e`c?gh3ib#k|bleelhd!k4cIfYbK7BkcjoftkZj-3Blsk%kkaEkPlzkrf:aO2weMbDj{f5eTa!a$fL8MePc f`kzf|lqkWjof$luk(lw0$a jvkRl$kO6+l8a{g9k/5~e#hLcwekjUj 04iMk7fTbrbthHeqdLlpgLb?l}5kcAlTkVkCj$bOjqlvjxg4l7kpbSlBk,g8e{gab!m6k_fPk{lJ52b+5_mw5kb/lHk f}fqjxb{mfl!mH5LgAkIb mml8mIc4le3Ql=dQcd0Jcflkf6eYajdEcnl_dKeomWcvk@jXedfRmA8!lmmElVmcmHcPa|mRjumjmOcUmQkp5ZcYb^lrc(mJkkc,mNk#nen5mO8wmpl:fTgjc}gekwd5grcJm4lZmGjtkenwk,dgnfl)nCningdonlmU8C15lFaQlk0nm)2xm2m-fUinm/bg1Bm;m#eTeV0.c b+k6nvk8h03Me+m|jtkFkHngkKc.nd9ynGnEe6nJgEdNnqnPm.einYk^kAeSl{nUi,m2bImakblWeFncnBeCn2ng9Rn}5Xjt9Xl/nK01j_mDn#04aZeWlOa,e(m`kBnxe_l4mOl6n`nBaaoq4_jtlcfCnmgigNgkozk1ovc_oXnpozgmm@25gpfmogl07Gjtltn@nEfxono^l+78mRaIo0mqe9eNlPjQgg9?mvmtm5j}o+lim?p9o2o/mFl1md0flYo@or3Cl%o`poplo|6{mOl.p0oVaM15f=f@lUd*lSnuo9jn6~oKngmioNmRmll,n6moldeHgbo%fdpflKljpcaTnopYm%fJ04o*pZ52gpkypHpEnAo;3(c3kfkIgzl(pogzoQ3$j%c35`kUohn;3(m~p{k#0En1pOkpqdpu6fp|m~dpj^gM9c9eeMp(kagRjlgT2+g+1M04h50T1m2f7;1w2xipiD9,iqiB34ith9iv0_g=2Ui4hYi000hahc1.hfhhhj0w1:2X2!hH0ki90V0o1mjOh.kG0R90001Bip2m0_hmhoqFq.3wiw129c0YhA3oi1i3i5hKk=q.hOk@0V0!1z1U3^qH22iDh!rahrg~0S0u0cbdi4q-q+0*q-2Xq:0nq=0K0V0P1n3V0(0;h/1:2fhj0s22h!rdqKhNh#9(0si(roi#0@9)r7h/hzh#0u1r21i41U9)0u1:qHrviSig0EiM1RqziQ2f22h$1j2Vhy2S2Tg(h/rkrir38Mr)i03oh`0!c}r@2W000kh rrg 1O3M2~i=dH1%1)1+jdi|1`291{2BaSj37Oj60Vj80Gja2NsBjfc!jh4wjji*qvo:8j0Cjpm a8s!qef+c1s(qikog6s,c=jE3VjG7)m+7,7.7:jPpDj1cp15m3o9l;p3oEs_8+d=oGp@sZ8qokcSs!2qnD5Xtgs-kQtjtdmTf:eLo4t5lQoZo!k38%oFphm{mGs!nzpn4_tDlys+kqlas%kqk.ksqnf9qpsRp6d3kxntlopIkcs!n?k!6ut#tItfkJtlf(t)tOpWc{oYp$m$tUaSgptXe*gtkWs!kYtF3$u0t*tMoppRs/k-3-q6sY9rs!e/nAt+oMs*uit-tJoTj@p2rVs~ovt^k28Jd/p=mbtC0$o?t%tno_qfu9lAu8jws!o ldlEaPusf8uredoBlNtspbp.m815n.ucpi7Gs!pmuDtGl*tiu,a q143u)kro1t4urmYm!t@p8p*uqk;e%tAoHpjklmes$u9pNuktMpQo}vcu@upe~nVeho3p$mydZmCt7c7v1s~u$tBv5s(p`uhtMb p~u,mPuJt(5Kn8n:uAn7tevAs)mgs(n4vFtnvLtptQnNuQmru`dSozeUa#n)k4n+t3t0k9v3tbuenbv8uKc(u.u3v^u;3Bs(nkpUvhgF15trp$fFp4vYk`oAn%twvZvsu{tzuyq7vKtEu+v`nCvCwmkmvSvDnIw0f/mrqsoZqrpXglnrfko.whudd`s(t$vP3Cn_vbu9e5umt+wPtOpVmruXu mup#uYlfttp5uvw9pewXm5v!mZtaf!s(u1wlu=eFv_w@0fu7vewOotpyov8DpCwgtYp?w:oJvMwOujwK6JwQvAuofCt;fbo(u}wZw+bpwxxlp-xn5Bp:t|5|vJvwfspLvGfAw_v}xztLwOuMwUv0nWdRw.wytsw-u|w!cC040N0Nv)15mzx5uzxyptx9v@ptxDv6x*v|x,pxn/t~m|s(g0vzwOvaxcvdpvx)pTu^52gGtSwzt=xkx!1Di.sTg*7rg,0Q9)1%i1slq)q-382_0%13hrq-jNr10j8Asimx0*0$0y1kq(9#5U1{0w0S0H0jxV0ryL0K0%0H2v3y0*1$7C0Y0K4A0m0K0n0#0N2x0N2_hqdG2$1U1B0Nys1e0$0%1d0*0H0N2r2!0R4.2Q2xr72r0=0G1)0w7E202n8D0TiFg~yss}9;5(i/g*0;0?0^04.

Exercice 2 :

Rendu de monnaie

Exercice 3 :

Colorier un graphe

Exercice 4 :

Livraison à Manhattan

Exercice 5 :

Mise en boîte

Exercice 6 :

Nombre minimal de quais