Le cadre
Les suites Hofstadter Figure-Figure \(R\) et \(S\) sont des suites d'entiers non nuls, complémentaires, définies par :
- \(R_0 = 1\), \(S_0 = 2\). (Définition, légèrement modifiée.)
- \(R_n = R_{n - 1} + S_{n-1}\), pour \(n > 0\).
- avec la suite \((S_{n})\) définie comme strictement croissante contenant tous les entiers absents de \((R_{n})\).
Les premiers termes sont :
- \(R = (1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, \cdots)\)
- \(S = (2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, \cdots)\)
Exercice
Coder une fonction suites_RS qui prend en paramètre un entier n >= 1 et qui renvoie un tuple de deux listes de longueur n des termes des suites R et S de Hofstadter.
Warning
\(0 < n < 10^5\)
On n'utilisera pas ni les ensembles, ni les dictionnaires, ni la récursivité, ni le module maths, ni le module functools.
On n'utilisera que les deux listes à construire comme structures de données.
On n'utilisera pas de boucle pour déterminer l'appartenance à \(R\), ni le test x in R (qui revient à faire une boucle).
On construira plutôt R et S à des vitesses distinctes.
Il n'est pas interdit de modifier un peu l'initialisation de R et S.
On pensera à réduire les listes si elles sont finalement un peu trop longues.
.128013 ],59/f.78r;nb _o=ylaepcwgu)vd4613kRmhétsP(S0+2[i: 050D0v0N0u0W0t0O0o0x0t0u0O0O0r010N0W0w010406050O0A0K0K0u0k0s040R0q0t0A0=0q0m050f0|0~10120`0w04051i1b1l0f1i0`0D0W0C0*0,0.0:0L0W0z0L0t1z0L0N0^050#0n0t0v1u0-0/011y1A1C1A0N1I1K1G0N0k1j0N0L1M1w010g0%0v0m0u0K0v010*150O0w0u0m0:0U1G1@1_1%1O1*1K1-1/0^0a0o0P0k0q0w0q0O0W180m0o0Z1=0k0k0v0x2g1b1~0m1j0f1#2t1Y1!1Z1H0D200:1C0m1,2d1G1r1t0+1N2D0W2F0m0q2J1G0w2m1j2r2t2X0{1^2h2L1(2Q0k0 0t0^0o0G2q2#0_2!1 2%1O2)2+2-0U2:1_2=2r2C012`0u2,040o0H2~2s0`312^0:34360o0E3a302#323g2-0d3k3c3m3e330q2*352-0F3r2?2$1v2_3w2{370i3B3d3E3f3G3y370j3K3t3M3v3x3h0e3S2@3U3o040G0S3Z3D2M3V3H0G2/1c2;3s3!3,3$0G2}3;2 3?3+2(3O360G393|3b3C3n410^0G3j453l3@403W4a3q4d3~484h3%3A4k473u3_3J4q3L3^493%3R4v3T4x4n0G3Y4B4f3F4n0U3)4d1m2V1b2J2w0D1!2B3u0x2R1:1j4R1k4P2Z4N4X0Z2W4C1(0I0^0Z0g3k4r3U0y2-4?4w2(0g0^0|2f0v0O0p0J0R4{4-1O0@040Q574I3f0^1a4N4|590^0B0X3r0o5p0o4@3^0^0J3k5r5j0:0q0^0r5w5s1(5a0V5d3 1O0K0W4a5I325a0c5D5y015L0^442Z5T5a0b5o5q5E2_0^564d5x585z5B5S5.015G5O3u5V043{5Y5=5Q5;5e5U5M044c5}615 5,5(0:5`4j665J0:682X5-615`4p6e5P0^5#4k5q6j6f330^0W0p0k606u5A045C695T5`3:6i6t320x0G0^030o2O1r0x1L0D0A2i0v0k0m0W6Y0o0M0t0M1/0m0N6X0o5v6r5%5T0m0^0k0p500C1_0N6A326C6E6i6a6v046:6n3u5@5i5=6@046x6z7b676p6 3u6C0T7k3#5*5^3U7a787p7e6y7r3,5!3r066s744/040y1y1K7o5t7w7g735T7m7K1(6H7R1O6C020t0N0l7U5f045h7u7z0^5n6;6s5p747d772;746C0h7y2(0^0u0w0w1,0D7`5k5b827$6_6{6}855?5l5$7.6K4s6w7x6F5=7m722;8f3U7T7-7.7:6^0p2U0q0x0L0$7(8n7@5:8j617;8a7t7?6?8h7N8K5~7j8F6B0^7n8R3n7q7h6u8J2 8t7M8I8Q2X7C8e8o3,7F0W4=8V4s0n0^238(848Y8W138`0B7#017W7Y7!8=7v8B8#5Z7+8d8,7/5T7F0g3w917d0O910q4_7e982s8-2(8@040k1_0z0v8`5c8|8g9v6`0A1s89963,7Q9J7S636I8O7i045R9M5)9E8w8y8A8 7,8*9d9d8$5+7)1(7^8a7d7}7 0m819C7s0^9B9+9V9l9@7*04908r7D8L9E886,9m8E7O7c8u9X8z2O7Ba35=7F7H1+9j9u8_9~5F9_9.5u8 a804020z7Z9j5g8`9#3=9(a47=998k0^7_ap9V2c0w9Aa19$6=ai0^ak7J9U3fan1,9Aas8~aM6g8caY920^axaza,7d9q4,9RaD3}aFaba(9{5/04aLa~75aOaQ9c7E6^0!0A6Z915a9`9Q6u8Ha)8b9SaAa}bf6oa03B0f4*0v2t2Ubt4Q1s4S2w2z2u0u1Jbw0f4R0`bG0!0$0(04.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)