Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 Entraide (supérieur) » Somme des termes d'une suite géométrique » 17-08-2021 10:28:53
- SébastienB
- Réponses : 4
Bonjour à tous, vive Bibm@th!
Ravi de voir que vous êtes toujours là.
Je suis en train de faire ce Mooc là : https://www.fun-mooc.fr/fr/cours/genius … ematiques/
Et il y a une suite géométrique définie par la relation de récurrence [tex]U_n = 0.6 \times U_{n - 1}[/tex]
Soit en définition explicite: [tex]U_n = U_1 \times 0.6_{n - 1}[/tex]
Jusque là ça va pas de problème j'ai compris. Mais je ne comprends pas l'égalité suivante:
[tex]U_1 + ... + U_n = \frac{1 - 0.6^n}{1 - 0.6}. U_1 = \frac{5}{2}(1 - 0.6^n) . U_1[/tex]
Comment on trouve ça ? Et d'ou ils viennent les [tex]\frac{5}{2}[/tex] ? Pourriez vous m'expliquer svp ?
D'avance merci.
#2 Re : Programmation » [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri » 10-07-2011 18:02:52
Re,
UP, j'ai répondu dans mon avant dernier message au dessus.
Vu que je ne suis ni Batcher, ni Bose ou Nelson mais un illustre inconnu, je ne pouvais pas le savoir!
Mais merci pour l'ajout.
@+
#3 Re : Programmation » [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri » 09-07-2011 16:22:51
Oui c'est fonctionnel. Ce tri semble performant.
public class BatcherVsBoseNelson{
static int nb_comparaisons = 0;
static int nb_echanges = 0;
static void sort(int a[]) {
int p, q, r, d, n, p2;
boolean fin;
n = a.length;
p = 1;
while (p <= n)
p = p << 1;
p2 = p >>> 1;
while (p >= 2) {
p = p >>> 1;
q = p2;
r = 0;
d = p;
fin = false;
while (!fin) {
for (int i = 0; i < n - d; i++) {
if ((i & p) == r) {
if (a[i] > a[i + d]) {
// Echange de i et i+d
int temp = a[i];
a[i] = a[i + d];
a[i + d] = temp;
nb_echanges++;
}
nb_comparaisons++;
}
}
if (q != p) {
d = q - p;
q = q >>> 1;
r = p;
fin = false;
} else
fin = true;
}
}
} // Fin du tri
public static void main(String args[]) {
int[] tab = new int[3000];
Random r = new Random();
for (int i = 0; i < 3000; i++) {
tab[i] = r.nextInt(3000);
}
long start = System.nanoTime();
sort(tab);
double tps = (System.nanoTime() - start) * 0.000000001;
System.out.println("Le temps d'execution pour le tri Batcher est: "
+ tps + " sec. "+nb_echanges+" echanges et "+nb_comparaisons+" comparaisons.");
for (int i = 0; i < 3000; i++) {
System.out.println(tab[i]);
}
}
}
1
1
2
3
6
8
11
12
14
18
20
21
22
23
27
28
29
33
33
33
34
36
38
41
43
43
44
45
46
47
47
47
47
49
50
50
51
51
52
54
55
55
56
56
57
57
57
58
60
61
61
63
63
64
64
65
66
67
67
68
68
70
72
73
73
73
74
74
74
75
76
77
77
78
78
81
82
82
83
83
84
84
84
86
87
87
88
89
89
91
93
93
94
94
94
96
96
98
98
98
99
100
100
102
103
103
105
106
107
107
107
108
109
109
110
111
112
115
118
120
120
123
123
125
125
127
128
128
129
129
130
130
130
131
131
132
132
133
134
135
135
137
139
140
141
142
142
144
147
149
150
152
155
160
164
166
170
170
171
172
175
176
178
180
180
180
180
180
182
182
183
184
184
184
184
187
188
189
191
192
192
193
193
194
194
194
196
198
200
200
201
206
206
207
208
208
208
209
210
211
211
212
214
215
220
221
222
223
223
226
226
230
230
231
232
233
233
234
234
235
236
238
239
239
240
240
241
242
243
243
243
244
245
247
248
249
251
251
252
252
253
254
255
255
259
259
260
261
262
263
263
265
266
269
269
269
269
270
271
272
273
273
273
277
277
278
278
279
279
280
280
282
282
283
283
285
287
288
288
290
290
290
292
292
292
294
294
295
296
296
297
297
297
298
300
300
301
305
305
307
307
309
310
310
311
311
312
314
315
315
315
318
319
319
319
321
321
323
323
326
329
329
330
331
331
331
336
337
338
338
339
339
341
341
342
343
343
345
346
346
347
347
348
351
353
356
357
359
359
360
360
361
362
362
363
363
364
364
365
368
369
370
370
370
371
372
375
375
376
378
381
382
383
386
387
387
388
389
389
390
391
391
392
392
392
395
396
396
396
399
399
400
401
402
402
404
405
405
405
406
406
408
408
408
411
415
415
416
416
417
418
419
420
423
423
423
424
424
425
426
427
428
428
428
429
429
431
435
437
443
445
445
445
449
449
450
450
452
455
455
455
455
456
457
459
460
464
465
465
466
466
467
467
467
467
467
469
469
470
473
478
481
481
482
482
486
487
489
491
492
496
498
500
501
502
502
503
504
505
507
507
512
512
513
515
517
517
518
520
520
522
523
525
525
527
527
528
529
529
529
530
531
531
532
533
534
534
535
535
535
536
538
538
539
542
542
544
544
546
547
548
548
549
549
552
554
556
559
561
564
566
568
569
570
572
572
575
575
578
579
579
580
581
582
583
583
587
587
588
590
593
594
594
595
599
599
600
601
604
604
606
607
609
610
610
611
613
614
614
614
617
620
621
621
622
622
624
625
626
627
629
631
632
634
636
638
639
639
640
641
641
642
643
643
644
646
648
649
653
653
654
654
658
659
660
660
662
665
665
667
667
670
670
671
671
673
674
674
674
675
675
676
676
676
678
678
681
683
684
688
689
690
691
692
693
697
697
697
697
699
699
700
701
701
702
703
703
703
703
704
704
704
704
705
706
706
707
708
708
708
708
709
712
714
715
716
717
717
718
720
722
726
726
727
728
729
729
730
731
732
732
732
734
735
735
736
736
737
737
742
744
744
745
746
746
746
747
750
752
752
753
756
756
757
758
758
759
759
760
760
760
762
762
762
762
764
764
764
767
769
770
770
771
775
775
776
778
779
779
780
782
783
783
784
784
785
785
785
786
788
788
789
792
793
793
795
796
797
797
798
798
799
800
800
800
801
802
804
804
805
805
806
808
808
808
809
812
812
813
814
815
816
819
819
819
821
821
821
822
823
825
826
828
828
828
829
829
832
832
833
833
835
836
837
839
839
841
842
843
843
843
845
846
846
847
849
852
852
854
855
856
856
857
857
859
859
859
860
860
860
861
862
864
866
866
868
871
872
875
876
877
881
884
884
886
889
889
889
890
892
892
893
893
895
896
897
897
899
900
900
902
903
904
905
906
906
909
911
911
911
911
912
912
913
913
914
914
916
917
919
921
924
924
924
925
926
927
928
928
929
929
930
930
932
936
936
937
938
939
941
942
947
947
948
949
952
953
953
957
957
958
959
959
960
962
965
965
965
966
969
970
971
972
972
972
973
975
976
977
977
979
980
981
983
984
984
985
987
988
989
990
993
994
996
997
999
999
1001
1003
1003
1005
1007
1007
1009
1010
1011
1014
1014
1014
1014
1016
1016
1017
1017
1017
1018
1018
1019
1020
1020
1023
1023
1024
1025
1025
1027
1027
1027
1029
1031
1031
1031
1031
1032
1033
1034
1035
1037
1039
1040
1040
1042
1043
1044
1046
1047
1052
1055
1057
1059
1059
1059
1059
1061
1062
1063
1065
1065
1065
1066
1068
1069
1071
1071
1073
1073
1076
1077
1080
1081
1082
1084
1085
1088
1088
1089
1090
1091
1091
1092
1093
1094
1095
1096
1098
1099
1099
1099
1099
1100
1101
1101
1102
1102
1104
1105
1106
1106
1106
1107
1109
1109
1110
1110
1111
1111
1112
1112
1115
1117
1118
1119
1120
1120
1121
1121
1121
1121
1121
1123
1124
1125
1125
1125
1127
1128
1128
1129
1129
1131
1132
1133
1133
1135
1135
1138
1138
1139
1141
1142
1143
1143
1144
1144
1144
1145
1146
1147
1147
1152
1153
1156
1157
1158
1158
1161
1162
1163
1164
1164
1165
1166
1167
1168
1168
1168
1169
1169
1169
1169
1170
1172
1172
1172
1172
1173
1173
1175
1175
1175
1176
1177
1177
1177
1178
1180
1181
1181
1181
1182
1182
1183
1183
1184
1184
1185
1186
1188
1189
1189
1190
1190
1196
1197
1197
1197
1200
1201
1201
1203
1203
1203
1204
1209
1210
1210
1211
1211
1211
1212
1212
1217
1217
1217
1219
1221
1222
1223
1223
1223
1224
1225
1225
1226
1226
1226
1226
1228
1229
1231
1232
1233
1234
1235
1236
1239
1239
1240
1241
1243
1245
1245
1245
1246
1247
1247
1247
1248
1248
1250
1254
1254
1255
1255
1255
1256
1258
1259
1259
1260
1262
1262
1262
1262
1263
1265
1265
1266
1267
1267
1269
1271
1271
1271
1271
1272
1272
1273
1273
1273
1274
1277
1277
1277
1279
1281
1281
1282
1283
1284
1284
1285
1285
1286
1288
1288
1288
1288
1288
1288
1289
1291
1292
1294
1294
1295
1296
1298
1298
1298
1298
1299
1302
1304
1305
1306
1306
1308
1309
1309
1310
1310
1311
1316
1316
1316
1318
1318
1318
1319
1321
1322
1324
1325
1327
1328
1329
1331
1331
1333
1333
1333
1334
1335
1337
1337
1338
1338
1338
1339
1341
1344
1345
1346
1346
1348
1348
1348
1349
1349
1350
1351
1352
1352
1352
1354
1355
1355
1355
1356
1359
1360
1361
1361
1362
1362
1362
1362
1362
1363
1363
1363
1363
1365
1365
1365
1366
1366
1368
1369
1369
1371
1371
1371
1373
1374
1375
1375
1376
1376
1377
1377
1378
1379
1379
1379
1379
1380
1382
1382
1383
1384
1385
1385
1386
1387
1387
1387
1387
1388
1388
1388
1389
1389
1389
1389
1390
1392
1392
1392
1392
1393
1394
1394
1397
1398
1399
1399
1399
1399
1400
1401
1402
1402
1402
1404
1405
1405
1406
1406
1407
1407
1407
1407
1408
1409
1413
1413
1413
1414
1415
1418
1419
1419
1420
1420
1421
1421
1422
1422
1422
1423
1424
1425
1426
1426
1428
1428
1430
1432
1435
1437
1438
1438
1438
1440
1440
1442
1442
1443
1444
1445
1445
1449
1452
1454
1454
1456
1457
1458
1460
1462
1462
1463
1464
1466
1468
1472
1472
1473
1473
1475
1479
1481
1481
1481
1482
1483
1484
1488
1490
1491
1492
1492
1493
1496
1499
1501
1503
1503
1505
1505
1506
1506
1508
1508
1509
1510
1511
1512
1512
1515
1515
1518
1520
1520
1521
1522
1524
1524
1525
1525
1528
1528
1528
1529
1530
1530
1532
1532
1533
1536
1537
1539
1539
1542
1543
1544
1544
1545
1547
1549
1549
1550
1552
1553
1553
1554
1555
1556
1557
1557
1557
1558
1559
1561
1562
1562
1562
1562
1562
1563
1563
1563
1569
1569
1570
1571
1573
1573
1574
1575
1579
1579
1580
1580
1581
1581
1582
1582
1583
1583
1584
1584
1584
1584
1585
1585
1585
1586
1586
1586
1587
1588
1588
1589
1589
1590
1592
1592
1596
1599
1600
1601
1601
1601
1602
1603
1605
1606
1607
1607
1607
1607
1608
1608
1608
1608
1608
1609
1610
1610
1610
1611
1613
1613
1613
1614
1614
1614
1614
1615
1617
1621
1623
1627
1628
1628
1628
1628
1629
1630
1631
1631
1632
1632
1633
1635
1636
1637
1637
1637
1638
1638
1640
1640
1641
1641
1642
1642
1645
1645
1646
1648
1651
1652
1652
1656
1657
1659
1659
1659
1659
1660
1660
1662
1667
1668
1669
1669
1670
1670
1670
1670
1671
1672
1672
1675
1676
1676
1676
1678
1679
1679
1679
1681
1682
1686
1686
1688
1689
1690
1690
1692
1692
1692
1693
1694
1695
1695
1697
1699
1699
1700
1702
1703
1704
1704
1705
1706
1706
1708
1708
1708
1708
1709
1710
1710
1711
1712
1712
1712
1713
1714
1714
1715
1715
1716
1717
1719
1720
1720
1721
1721
1722
1725
1727
1728
1729
1730
1730
1733
1734
1738
1740
1743
1743
1747
1748
1752
1752
1752
1753
1753
1754
1755
1755
1757
1757
1757
1759
1760
1760
1761
1762
1763
1763
1768
1769
1769
1771
1771
1771
1772
1772
1773
1773
1774
1775
1776
1776
1778
1778
1778
1779
1779
1779
1780
1781
1782
1783
1783
1786
1787
1787
1789
1790
1791
1791
1795
1795
1796
1797
1798
1800
1800
1801
1802
1803
1803
1805
1805
1807
1808
1808
1809
1810
1811
1812
1812
1812
1812
1812
1812
1814
1815
1815
1816
1819
1821
1821
1822
1823
1824
1824
1825
1826
1826
1828
1828
1834
1834
1836
1837
1837
1838
1839
1841
1843
1843
1843
1844
1844
1846
1847
1847
1848
1849
1851
1851
1851
1852
1853
1854
1856
1857
1859
1859
1865
1866
1868
1868
1869
1869
1870
1870
1873
1877
1880
1880
1880
1881
1882
1882
1886
1887
1887
1887
1888
1889
1890
1891
1891
1892
1894
1894
1895
1895
1896
1896
1900
1901
1907
1911
1912
1913
1913
1914
1915
1915
1915
1917
1917
1918
1918
1919
1921
1922
1923
1926
1926
1927
1927
1929
1929
1930
1931
1933
1933
1941
1943
1945
1946
1946
1946
1947
1948
1949
1949
1950
1950
1952
1954
1955
1955
1956
1958
1958
1958
1958
1958
1960
1960
1960
1961
1961
1963
1964
1966
1966
1967
1967
1967
1968
1970
1971
1972
1972
1972
1973
1974
1975
1976
1978
1978
1979
1980
1982
1983
1983
1984
1984
1985
1985
1985
1985
1986
1988
1989
1989
1991
1991
1992
1993
1994
1995
1995
1995
1996
1998
2000
2001
2001
2001
2002
2002
2003
2004
2005
2006
2006
2010
2010
2010
2012
2014
2018
2018
2021
2021
2022
2022
2022
2023
2027
2027
2030
2031
2031
2032
2034
2035
2037
2037
2037
2038
2041
2042
2042
2045
2045
2046
2046
2047
2049
2050
2051
2051
2054
2056
2057
2057
2059
2059
2060
2060
2060
2060
2061
2061
2061
2061
2063
2063
2064
2064
2065
2066
2066
2068
2068
2068
2069
2069
2069
2071
2071
2073
2073
2075
2076
2077
2077
2078
2078
2079
2079
2080
2081
2081
2084
2084
2084
2086
2086
2088
2089
2089
2089
2089
2089
2093
2094
2094
2096
2097
2097
2099
2100
2100
2102
2103
2103
2103
2103
2103
2106
2107
2109
2109
2110
2110
2111
2113
2113
2113
2113
2115
2118
2118
2121
2121
2121
2122
2122
2122
2122
2123
2123
2124
2124
2125
2130
2131
2132
2134
2135
2137
2137
2138
2140
2141
2142
2145
2145
2146
2146
2147
2147
2149
2151
2151
2152
2154
2155
2156
2158
2158
2158
2161
2162
2165
2166
2167
2167
2168
2170
2170
2170
2171
2172
2175
2177
2177
2178
2179
2180
2182
2182
2183
2183
2183
2184
2184
2187
2188
2189
2193
2194
2195
2196
2197
2199
2203
2203
2203
2205
2205
2206
2206
2207
2208
2209
2212
2212
2214
2217
2217
2217
2218
2219
2219
2219
2220
2221
2221
2222
2222
2222
2223
2224
2225
2226
2226
2227
2227
2227
2228
2228
2228
2230
2232
2232
2232
2233
2234
2235
2235
2241
2243
2244
2244
2245
2245
2246
2247
2249
2249
2249
2250
2250
2250
2254
2255
2256
2258
2259
2260
2260
2261
2262
2262
2262
2264
2264
2266
2266
2267
2267
2268
2269
2271
2272
2273
2274
2274
2274
2275
2277
2277
2278
2278
2279
2281
2281
2281
2282
2283
2286
2288
2289
2290
2294
2296
2297
2299
2299
2300
2301
2302
2303
2304
2306
2306
2307
2308
2309
2311
2311
2312
2313
2313
2314
2315
2315
2316
2316
2316
2317
2317
2320
2321
2323
2323
2323
2326
2326
2327
2329
2331
2331
2332
2333
2334
2335
2336
2338
2338
2342
2342
2342
2347
2347
2348
2352
2352
2354
2355
2357
2357
2359
2361
2363
2363
2364
2364
2365
2365
2366
2366
2368
2369
2370
2370
2370
2371
2373
2374
2374
2374
2376
2377
2377
2377
2378
2378
2379
2380
2381
2382
2383
2384
2385
2386
2386
2387
2388
2388
2388
2391
2392
2392
2392
2393
2395
2396
2396
2396
2396
2398
2399
2399
2399
2400
2402
2403
2403
2404
2406
2408
2410
2410
2412
2413
2414
2415
2416
2416
2419
2421
2422
2423
2423
2423
2423
2427
2428
2429
2432
2434
2435
2435
2436
2439
2440
2440
2441
2441
2443
2443
2443
2447
2447
2448
2450
2450
2453
2454
2455
2455
2457
2458
2458
2458
2459
2460
2460
2460
2461
2461
2463
2464
2468
2468
2469
2469
2470
2471
2471
2473
2473
2474
2476
2476
2476
2477
2478
2479
2479
2480
2482
2483
2484
2485
2485
2489
2492
2496
2497
2497
2498
2499
2500
2500
2501
2503
2504
2505
2505
2505
2505
2507
2508
2509
2510
2511
2511
2512
2512
2513
2513
2515
2515
2516
2516
2517
2517
2519
2521
2522
2522
2524
2524
2525
2526
2526
2528
2528
2528
2529
2532
2533
2533
2533
2533
2534
2536
2536
2536
2537
2537
2538
2539
2539
2539
2540
2540
2540
2542
2542
2544
2545
2546
2546
2546
2546
2548
2550
2550
2552
2554
2555
2555
2555
2557
2559
2559
2561
2561
2562
2563
2564
2564
2565
2568
2568
2568
2569
2571
2574
2576
2578
2579
2580
2581
2581
2581
2582
2582
2583
2585
2586
2588
2589
2589
2591
2592
2592
2594
2595
2596
2598
2600
2600
2602
2602
2604
2606
2607
2608
2609
2613
2614
2618
2619
2619
2621
2623
2626
2627
2628
2628
2629
2629
2629
2630
2631
2632
2633
2633
2634
2635
2635
2635
2635
2636
2638
2638
2639
2643
2645
2645
2647
2647
2647
2647
2648
2649
2650
2650
2651
2651
2652
2653
2653
2656
2657
2658
2658
2660
2660
2663
2665
2666
2667
2671
2674
2675
2675
2676
2676
2677
2677
2677
2677
2678
2678
2678
2679
2679
2679
2679
2680
2682
2682
2683
2684
2684
2685
2685
2686
2687
2688
2690
2693
2694
2695
2697
2698
2698
2698
2699
2699
2701
2702
2703
2704
2705
2709
2709
2712
2713
2714
2715
2715
2715
2716
2716
2716
2717
2717
2717
2718
2718
2719
2719
2720
2722
2723
2724
2725
2725
2726
2726
2728
2729
2731
2732
2733
2734
2736
2737
2739
2739
2741
2741
2744
2744
2745
2745
2746
2748
2749
2750
2751
2753
2754
2754
2754
2754
2756
2757
2757
2757
2757
2758
2758
2758
2760
2762
2764
2767
2767
2768
2769
2769
2772
2772
2773
2774
2776
2777
2777
2778
2779
2780
2781
2783
2783
2785
2785
2786
2786
2787
2787
2791
2792
2792
2793
2794
2794
2795
2795
2797
2797
2798
2799
2799
2800
2801
2803
2804
2805
2806
2807
2807
2811
2813
2814
2814
2815
2815
2815
2818
2820
2822
2824
2824
2825
2826
2828
2830
2831
2832
2832
2834
2837
2837
2838
2839
2843
2843
2843
2844
2846
2847
2848
2853
2853
2855
2856
2856
2857
2857
2859
2861
2863
2863
2865
2866
2867
2868
2869
2870
2870
2872
2872
2872
2872
2873
2873
2873
2875
2876
2877
2878
2879
2880
2881
2882
2882
2885
2887
2887
2887
2888
2890
2892
2893
2894
2894
2895
2897
2898
2898
2899
2899
2899
2900
2902
2903
2903
2903
2904
2904
2905
2905
2906
2906
2906
2906
2907
2908
2908
2909
2913
2913
2913
2913
2919
2919
2920
2921
2923
2924
2925
2926
2928
2930
2930
2930
2931
2933
2933
2936
2937
2937
2938
2939
2939
2940
2941
2942
2943
2944
2945
2947
2947
2948
2948
2948
2949
2950
2951
2952
2953
2954
2954
2954
2958
2958
2958
2959
2959
2960
2962
2962
2963
2964
2965
2965
2966
2966
2967
2967
2968
2968
2970
2971
2972
2973
2974
2978
2979
2979
2981
2981
2982
2984
2985
2985
2989
2990
2991
2993
2994
2995
2995
2996
2999
tri de Batcher en Python:
http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort
Pour le Java, voilà un autre site connu mais dont le lien ici a le mérite de pointer sur un complément d'informations utiles et exactes:
http://www.commentcamarche.net/contents … avaop.php3
@+
#4 Re : Programmation » [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri » 09-07-2011 12:24:35
Bonjour,
Super ces mesures. Chez moi le tri par casiers est cent fois plus performant que le tri à l'aide d'un arbre binaire de recherche pour trier une suite d'entier. Mais l'arbre binaire a l'avantage de ranger les éléments dans l'ordre en fonction de leur précédent lors du stockage de ces derniers. Donc je dirai que tout dépend du contexte pour choisir l’implémentation de telle ou telle méthode de tri.
Ci dessous mon programme pour tester le tri par arbre binaire de recherche et le tri par casiers en Java:
import java.util.Stack;
/**
* @see http://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf
*
* @param <Key>
* @param <Value>
*/
public class BST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
private Node root;
private class Node {
Key key;
Value val;
Node left, right;
Node(Key key, Value val) {
this.key = key;
this.val = val;
}
}
private class BSTIterator implements Iterator<Key> {
private Stack<Node> stack = new Stack<Node>();
private void pushLeft(Node x) {
while (x != null) {
stack.push(x);
x = x.left;
}
}
BSTIterator() {
pushLeft(root);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Key next() {
Node x = stack.pop();
pushLeft(x.right);
return x.key;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
private Node put(Node x, Key key, Value val) {
if (x == null)
return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp == 0)
x.val = val;
else if (cmp < 0)
x.left = put(x.left, key, val);
else if (cmp > 0)
x.right = put(x.right, key, val);
return x;
}
@Override
public Iterator<Key> iterator() {
return new BSTIterator();
}
public Value get(Key key) {
Node x = root;
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x.val;
else if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
}
return null;
}
public void put(Key key, Value val) {
root = put(root, key, val);
}
/**
* @see http://www.dailly.info/ressources/tri/java/casier.html
* @param tableau
*/
public static void triCasier(int tableau[]) {
int longueur = tableau.length;
// on parcours le tableau afin d'en récupérer les valeurs minimales et
// maximales
int mini = tableau[0];
int maxi = tableau[0];
for (int i = 1; i < longueur; i++) {
if (mini > tableau[i]) {
mini = tableau[i];
}
if (maxi < tableau[i]) {
maxi = tableau[i];
}
}
// on construit un tableau contenant le nombre d'entiers maxi-mini+1
int tmpLong = maxi - mini + 1;
int tmpTableau[] = new int[tmpLong];
// on initialise le tableau à 0
for (int i = 0; i < tmpLong; i++) {
tmpTableau[i] = 0;
}
// puis on increment le compteur correspondant à chaque entier trouvé
for (int i = 0; i < longueur; i++) {
tmpTableau[tableau[i] - mini]++;
}
// enfin, on reconstitue le tableau initial classé
int compt = 0;
for (int i = 0; i < tmpLong; i++) {
while (tmpTableau[i] > 0) {
tableau[compt] = mini + i;
tmpTableau[i]--;
compt++;
}
}
}
public static void main(String args[]) {
System.out.println("Tri par arbre binaire de recherche vs Tri par casiers");
BST<Integer, Integer> bst = new BST<Integer, Integer>();
System.out.println("Avant:");
int[] tab = new int[2936];
for (int i = 3000; i >= 65; i--) {
System.out.print((char) i);
bst.put(i, i);
tab[i-65]=i;
System.out.print("("+tab[i-65]+") ");
}
System.out.println();
Integer k = new Integer(65);
long start = System.nanoTime();
while ((k = bst.get(k)) != null)
k++;
double tps = (System.nanoTime() - start) * 0.000000001;
System.out
.println("Le temps d'execution pour le tri a l'aide d'un arbre binaire de recherche est: "
+ tps + " sec.");
start = System.nanoTime();
triCasier(tab);
tps = (System.nanoTime() - start) * 0.000000001;
System.out
.println("Le temps d'execution pour le tri par casier est: "
+ tps + " sec.");
k = 65; // Réinitialiser le noeud de départ
System.out.println("Après:");
while ((k = bst.get(k)) != null) {
System.out.print((char) k.intValue());
System.out.print("("+tab[k-65]+") ");
k++;
}
}
}
Avant:
?(3000) ?(2999) [...] Z(90) Y(89) X(88) W(87) V(86) U(85) T(84) S(83) R(82) Q(81) P(80) O(79) N(78) M(77) L(76) K(75) J(74) I(73) H(72) G(71) F(70) E(69) D(68) C(67) B(66) A(65)
Le temps d'execution pour le tri a l'aide d'un arbre binaire de recherche est: 0.059544678000000004 sec.
Le temps d'execution pour le tri par casier est: 5.86445E-4 sec.
Après:
A(65) B(66) C(67) D(68) E(69) F(70) G(71) H(72) I(73) J(74) K(75) L(76) M(77) N(78) O(79) P(80) Q(81) R(82) S(83) T(84) U(85) V(86) W(87) X(88) Y(89) Z(90) [...] ?(2999) ?(3000)
@+
#5 Re : Programmation » [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri » 02-07-2011 11:24:17
Le spécialiste dont il était question a apparemment mis des liens vers d’intéressants documents depuis sa page web.
Les slides à cette adresse sont super bien je trouve:
http://www.cs.princeton.edu/~rs/AlgsDS07/
Par exemple l'utilisation d'un arbre binaire de recherche me paraît efficace:
http://www.cs.princeton.edu/~rs/AlgsDS0 … hTrees.pdf
J'espère que cela t'aidera à trouver les algorithmes de tri que tu recherches.
@+
#6 Re : Programmation » [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri » 02-07-2011 10:26:48
Salut BibM@th!
Si vous permettez, je souhaite apporter ma modeste contribution à cette intéressante discussion.
Une fois un personnage important a dit que le récursif était élégant.
Aujourd'hui , je me demande comment justifier le choix de ce paradigme, je veux dire de la programmation fonctionnelle ?
LISP est bien expliqué sur cette page web j'ai trouvé :http://www.dontveter.com/basisofai/13.html
L'algorithme QuickSort en LISP ci dessous fonctionne bien:
(setq i '(e iteration))
(defun qs (l)
(let* ((twolists nil)
(left nil)
(right nil)
(sortedleft nil)
(sortedright nil)
)
(cond ((null l) nil)
(t (setq twolists (partition (car l) (cdr l)))
(print iteration)
(print i)
(setq iteration (+ iteration 1))
(setq left (car twolists))
(setq right (cdr twolists))
(setq sortedleft (qs left))
(setq sortedright (qs right))
(append sortedleft
(cons (car l) sortedright))))))
(defun partition (key l) (partition2 key l nil nil))
(defun partition2 (key l left right)
(cond ((null l) (cons left right))
(t (cond ((> (car l) key)
(partition2 key (cdr l) left
(cons (car l) right)))
(t (partition2 key (cdr l)
(cons (car l) left)
right))))))
1
(E ITERATION)
2
(E ITERATION)
3
(E ITERATION)
4
(E ITERATION)
5
(E ITERATION)
6
(E ITERATION)
7
(E ITERATION)
8
(E ITERATION)
9
(E ITERATION)
10
(E ITERATION)
(-1 0 0 0 1 20 43 46 71 88)
Ci dessous, comme souvenance, voici la première version de cet algorithme connu que j'avais codé en C compréhensible:
#include <stdlib.h>
static int compteurPermutation = 0;
void permut(int* i1, int* i2)
{
*i1 = *i1 + *i2;
*i2 = *i1 - *i2;
*i1 = *i1 - *i2;
}
void quicksort (int tableau[], int debut, int fin)
{
int begin = debut;
int end = fin;
int mil = (begin + end ) / 2;
do
{
while ((tableau[begin] < tableau[mil]) && (begin < mil)) begin++;
while ((tableau[end] > tableau[mil]) && (end > mil)) end--;
if ( tableau[begin] > tableau[end] )
{
printf("%d permutation...\n", ++compteurPermutation);
permut (&tableau[begin], &tableau[end]);
}
begin++;
end--;
} while ( begin < end );
if (begin < fin ) quicksort(tableau, begin, fin);
if (end > debut ) quicksort(tableau, debut, end);
}
int main()
{
int i;
int tab[10] ={1};
tab[5] = 88;
tab[6] = 71;
tab[9] = 43;
tab[1] = 20;
tab[2] = 46;
tab[3] = -1;
printf("Affichage du tableau avant le tri:\n");
for ( i = 0; i < 10; i++ )
{
printf("%d ", tab[i] );
}
printf("\n");
quicksort(tab, 0, 9);
printf("Affichage du tableau apres le tri:\n");
for ( i = 0; i < 10; i++ )
{
printf("%d ", tab[i] );
}
return 0;
}
@+
#7 Re : Cryptographie » Ephemeral Diffie Hellman » 03-04-2011 22:01:05
C'est pareil , sauf que :
"In Ephemeral-Static mode, the recipient has a static (and certified)
key pair, but the sender generates a new key pair for each message
and sends it using the originatorKey production."
http://www.ietf.org/rfc/rfc2631.txt
[tex]\rule{\linewidth}{2mm}[/tex]
@+
#8 Re : Cryptographie » décomposition en facteurs premiers » 15-02-2011 19:22:39
Re, bonjour
Extraordinaire!
alors [tex]\forall n \in \mathbb{N}^*, \exists!(\alpha_p)_{p\in\mathcal{P}}\in\mathbb{N}^{(\mathcal{P})}: n = \prod_{p\in\mathcal{P}} p^{\alpha_p}[/tex] est vrai et tout à fait exact
merci
@+
#9 Cryptographie » méthode mathématique pour le calcul d'une clé publique rsa » 14-02-2011 19:11:30
- SébastienB
- Réponses : 0
bonjour,
pour la procédure de cryptage rsa, on prend deux grands nombre premiers P et Q, ensuite, on calcule une des deux constituantes de la clé publique qui permet d'élaborer la valeur commune aux clés de cryptage et de décryptage [tex]N = P \times Q[/tex]
La clé publique E doit être premier avec [tex]Z = (P-1)\times(Q-1)[/tex]
Or il parait que E doit être choisie au hasard et c'est justement le sujet de ma question plus bas
Si on prend E = 1, ça marcherait mais la clé privée serait égale aussi à E, donc ce n'est pas possible. De même je pense qu'il vaut mieux éviter que la clé privée D soit égale à E et que c'est la le pont faible.
La clé privé est choisie de façon à respecter l'équation [tex]E\times D= k \times Z + 1[/tex] , ou que [tex]E \times D = 1 ~ modulo ~ Z[/tex] d'après le support que j'ai
[tex]E \times D ~ mod ~ Z ~ = ~ 1[/tex] m'a permis d'écrire cet algorithme qui fonctionne pour le calcul de la clé privée avec par exemple:
[tex]P = 29, Q = 37[/tex]
[tex]Z = ( P - 1 ) \times ( Q - 1 )[/tex]
[tex]E = 71[/tex]
[tex]D = E + 1[/tex]
[tex]\text{WHILE}((D \times E)~ mod ~Z~ != ~1)[/tex]
[tex]~~D~=~D~+~1[/tex]
[tex]\text{ENDWHILE}[/tex]
ensuite, pour crypter un bloc M on fait [tex]C = M^E ~mod~ N[/tex]
et pour décrypter, [tex]M = C^D ~mod~ N[/tex]
le fait que c'est la clé secrète qui permette de décrypter est génial je trouve mais je voudrais savoir si on pourrait trouver une méthode mathématique qui permettrait de calculer une valeur de la clé publique E ?
merci bien si vous pouvez me répondre
@+
#10 Cryptographie » décomposition en facteurs premiers » 14-02-2011 18:52:39
- SébastienB
- Réponses : 4
bonjour,
dans le cadre de recherches connexes à un cours sur le cryptage rsa, je suis tombé sur cette page web http://fr.wikipedia.org/wiki/D%C3%A9com … s_premiers ou on peut lire que Tout nombre naturel n non nul peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate., suivi de [tex]\forall n \in \mathbb{N}^*, \exists!(\alpha_p)_{p\in\mathcal{P}}\in\mathbb{N}^{(\mathcal{P})}: n = \prod_{p\in\mathcal{P}} p^{\alpha_p}[/tex]
or si le point d'exclamation représente une négation et la bonne formule serait plutôt : [tex]\forall n \in \mathbb{N}^*, \exists(\alpha_p)_{p\in\mathcal{P}}\in\mathbb{N}^{(\mathcal{P})}: n = \prod_{p\in\mathcal{P}} p^{\alpha_p}[/tex]
avez vous un point de vue sur la formulation mathématique qui est VRAIE svp ?
ci dessous, j'ai codé rapidement en java une classe de la représentation abstraite que je me suis faite de la formule juste:
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;
public class PrmFact {
private int N;
PrmFact(int n){
N = n;
}
private boolean estPremier(int n){
boolean p = true;
for (int i = 2; i < n; i++){
if ( n % i == 0 ){
p = false;
break;
}
}
return p;
}
private void processHashtable(Hashtable<Integer,Integer> h, int i){
boolean present = false;
for (Integer e : h.keySet()){
if ( e.intValue() == i){
present = true;
break;
}
}
if (present)
h.put(i, h.get(i).intValue()+1);
else
h.put(i, 1);
}
private Hashtable<Integer,Integer> decompose(){
Hashtable<Integer,Integer>res = new Hashtable<Integer, Integer>();
int i = 2, k;
while ( i <= N ){
k = i;
if ( estPremier(i) ){
if ( N % i == 0 ){
processHashtable(res, i);
N /= i;
i = k;
} else
i++;
}else
i++;
}
return res;
}
private void afficher(Hashtable<Integer,Integer> h){
System.out.print("1");
Vector<Integer> v = new Vector<Integer>(h.keySet());
Collections.sort(v);
for (Enumeration<Integer> e = v.elements(); e.hasMoreElements();){
Integer key = e.nextElement();
System.out.print(" x "+key.intValue()+"^"+h.get(key).intValue());
}
System.out.println("");
}
public void decPowPrems(){
System.out.print(this.N + " = ");
this.afficher(this.decompose());
}
public static void main(String[] args){
PrmFact p0 = new PrmFact(5);
p0.decPowPrems();
PrmFact p1 = new PrmFact(10);
p1.decPowPrems();
PrmFact p2 = new PrmFact(12);
p2.decPowPrems();
PrmFact p3 = new PrmFact(28);
p3.decPowPrems();
PrmFact p4 = new PrmFact(1008);
p4.decPowPrems();
PrmFact p5 = new PrmFact(100000);
p5.decPowPrems();
PrmFact p6 = new PrmFact(1000000);
p6.decPowPrems();
PrmFact p7 = new PrmFact(2100000);
p7.decPowPrems();
}
}
10 = 1 x 2^1 x 5^1
12 = 1 x 2^2 x 3^1
28 = 1 x 2^2 x 7^1
1008 = 1 x 2^4 x 3^2 x 7^1
100000 = 1 x 2^5 x 5^5
1000000 = 1 x 2^6 x 5^6
2100000 = 1 x 2^5 x 3^1 x 5^5 x 7^1
#11 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » Des images 4D : Oeuvres d'art inédites » 26-07-2010 21:38:20
merci pour les liens. superbe en effet!
++
#12 Re : Entraide (supérieur) » Théorème des écarts complémentaires » 30-12-2009 12:01:06
Bonjour,
Merci pour les slides.
Dans cet exercice, les 5 contraintes primales sont saturées car [tex]y^*_i > 0[/tex].
De plus, [tex]\forall a_{ij}, a=1[/tex].
Pour [tex]z = 108900 = w[/tex] on a [tex]x^* = (440,20,20,0,400,0,0,0,230)[/tex] et [tex]y^* = (80,50,70,70,20)[/tex].
Or dans [tex]y^*[/tex], la 3è contrainte n'est pas respectée [tex]80 + 20 \gneq 110[/tex]
[tex]\begin{cases}y_3^*(b_3 - \sum_{j=1}^{n} a_{ij} x_j^*) = 0 \\ x_3^*(c_3 - \sum_{i=1}^{m}y_i^* a_{ij}) \neq 0 \end{cases}[/tex]
[tex]\begin{cases} 70 ( 230 - (0 + 0 + 230 )) = 0 \\ 20 ( 110 - ((y1 = 80) + (y5 = 20))) \neq 0 \end{cases}[/tex]
Donc cette solution n'est pas optimale.
La solution optimale est : [tex]109100=\begin{cases}x^* = (230,0,250,0,400,0,210,20,0) & \text{Ct marginaux dual} \\ y^* = (80,50,60,70,30) & \text{Ct marginaux primal} \end{cases}[/tex]
C'est tout juste ?
#13 Entraide (supérieur) » Théorème des écarts complémentaires » 28-12-2009 15:55:43
- SébastienB
- Réponses : 4
Salut BibM@th !
Bonnes fêtes de fin d'année.
Voila ce qui m'amènes:
maximiser:
[tex]z = 80x_{1,1} + 140x_{1,2} + 110x_{1,3} + 40x_{2,1} + 120x_{2,2} + 70x_{2,3} + 60x_{3,1} + 130x_{3,2} + 90x_{3,3}[/tex]
sous:
[tex]\begin{cases}x_{1,1} + x_{1,2} + x_{1,3} \le 480 & \text{(y1)}\\ x_{2,1} + x_{2,2} + x_{2,3} \le 400 & \text{(y2)}\\ x_{3,1} + x_{3,2} + x_{3,3} \le 230 & \text{(y3)} \\ x_{1,2} + x_{2,2} + x_{3,2} \le 420 & \text{(y4)} \\ x_{1,3} + x_{2,3} + x_{3,3} \le 250 & \text{(y5)} \end{cases}[/tex]
[tex]x_{1,1} \ge 0 , x_{1,2} \ge 0 , x_{1,3} \ge 0 , x_{2,1} \ge 0 , x_{2,2} \ge 0 , x_{2,3} \ge 0 , x_{3,1} \ge 0 , x_{3,2} \ge 0 , x_{3,3} \ge 0[/tex]
La représentation duale de ce programme linéaire est plus simple si je ne me trompes pas:
minimiser:
[tex]w = 480y1 + 400y2 + 230y3 + 420y4 + 250y5[/tex]
sous:
[tex]\begin{cases}y1 & \ge 80 \\ y1 + y4 & \ge 140 \\ y1 + y5 & \ge 110 \\ y2 & \ge 40 \\ y2 + y4 & \ge 120 \\ y2 + y5 & \ge 70 \\ y3 & \ge 60 \\ y3 + y4 & \ge 130 \\ y3 + y5 & \ge 90 \end{cases}[/tex]
[tex]y1 \ge 0 , y2 \ge 0 , y3 \ge 0 , y4 \ge 0 , y5 \ge 0[/tex]
La question est de savoir si [tex] 440x_{1,1} + 20x_{1,2} + 20x_{1,3} + 400x_{2,2} + 230x_{3,3}[/tex] (cela fait 108900) est optimale à l'aide du théorème des écarts complémentaires ?
La résolution par le simplex à l'aide d'un logiciel donne:
MAX Z = 109100.0000
VARIABLES DE DÉCISION
Variable Valeur Couts réduits
------------------------------------------------------
x11 230.0000 0.0000
x12 0.0000 -10.0000
x13 250.0000 0.0000
x21 0.0000 -10.0000
x22 400.0000 0.0000
x23 0.0000 -10.0000
x31 210.0000 0.0000
x32 20.0000 0.0000
x33 0.0000 0.0000
------------------------------------------------------
CONTRAINTES
Contrainte Elasticicité? Couts marginaux
------------------------------------------------------
c1 0.0000 80.0000
c2 0.0000 50.0000
c3 0.0000 60.0000
c4 0.0000 70.0000
c5 0.0000 30.0000
------------------------------------------------------
Au passage, savez vous ce que signifient "Couts réduits", "Elasticité" et "Couts marginaux" dans cette solution ?
Et la réponse à la question est : bien sur que non car l'optimum a été trouvé pour une valeur de 109100 avec [tex]230x_{1,1}, 250x_{1,3}, 400x_{2,2}, 210x_{3,1} \text{et} 20x_{3,2}[/tex] mais auriez vous le théorème des écarts complémentaires s'il vous plaît ? et surtout pourriez vous me l'expliquer ?
Merci d'avance
@+
#14 Re : Programmation » Cryptage et Decryptage. » 26-08-2009 12:23:57
Bonjour,
J'ai pris la base 255 car il y a 255 caractères dans mon alphabet. La première de mes problématiques sur ce sujet était de trouver une table de caractères disponible sur tous les ordis et j'ai utilisé celle qui correspond en fait à Windows OEM - cp850 (multilingual Latin I) (http://pythonfacile.free.fr/python/codepages.html)
Ensuite, j'ai utilisé un entier long (long long = __int64 = entier codé sur 64 bits) qui permets donc de stocker une valeur maximum de [tex]2^{65} - 1 = 36893488147419103231[/tex]
et [tex]255^9 - 1 = 4558916353692287109374[/tex] , donc il y avait bien un dépassement de capacité.
par contre [tex]\frac{\ln{(\text{mot représenté en décimal})}}{\ln{(\text{base})}} = \text{longeur du mot}[/tex]
et [tex]\frac{\ln{(\text{nombre en base 10})}}{\ln{(10)}} = \text{longeur du nombre = nombre de chiffres}[/tex]
?
En utilisant un long double pour ma variable 'enc', je n'ai plus le problème de limite et je peux calculer des mots de plus de 26 lettres et ensuite calculer le modulo avec la fonction fmodl, mais là, ça décrypte bien la fin du mot mais pas le début (perte de précision paradoxalement). Donc il faut bien que j'utilise exclusivement des types entiers, pourquoi ça ne marche plus avec des réeels ?
Pour finir, je passerai le code en base 36 à la prochaine étape et j'esserai de poster un code un peu + propre...
Mais dans l'absolu, je pense qu'un alphabet disponible sur toutes les machines est bien [tex]\mathbb{B} = \{0,1\}[/tex] et que toute problématique en informatique revient en fait à faire des décalages avec les mots de cet alphabet dans [tex]\mathbb{B}^*[/tex].
Merci :)
@+
#15 Re : Programmation » Cryptage et Decryptage. » 23-08-2009 21:44:43
Bonjour,
Merci pour cette solution de cryptage. Ça m'a donné des idées mais je rencontre un petit problème technique:
-Comment faire pour utiliser un dictionnaire implicite, par exemple la table de caractères latin1 (ISO8859-1) qui comprend les 127 caractères du code ASCII + les caractères accentués et des caractères spéciaux, soit 255 caractères en tout ?
Avec mon code, si le mot dépasse 8 caractères, ça ne marche pas:
#include<string>
#include<cmath>
#include<cstdlib>
#include<sstream>
#include<algorithm>
using namespace std;
int main(){
//char dico[26] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
string s; //Texte à crypter
int j,l; //Indice de chaque caractère et longeur de la chaîne de caractères
long long enc=0; //Mot encodé en base 10
long long k; //Coefficient multiplicateur
ostringstream o; //Flux de sortie
unsigned char uc; //Caractère non signé utilisé pour obtenir le code du caractère en base 10 sur la page de code latin1
char buffer[64]; //Mémoire tampon de changement de base du mot encodé
cout << "Tapez un mot "<< char(0x85) << " crypter:"; getline ( cin , s );
l = s.length();
for (j=0;j<39;j++) cout << "--";
cout << endl;
/* CRYPTAGE
*
**************/
for ( j=0; j<l; j++ ){
uc = s.at(j); //Récupérer le caractère uc dans la chaîne s à l'indice j
k = long long(pow(255.0,j)); //Calculer un coefficient multiplicateur
enc += int(uc) * k; //Calculer le mot encodé en base 10
cout << s.at(j) << ":" << int(uc) << "*" << k << ";u(n-1)+u(i)=" << enc << endl;
}
for (j=0;j<39;j++) cout << "--";
cout << endl;
cout << "MOT CRYPT"<<char(0x90)<<" en base 10: "<< enc << endl;
for (j=0;j<39;j++) cout << "--";
cout << endl;
//_itoa(enc,buffer,36); //Convertir en base 36 pour raccourcir le mot
//o << buffer;
//cout << endl << o.str() << endl;
//s = o.str();
//cout << s.c_str() << endl;
//enc = strtol(s.c_str(),NULL,36); //Convertir en base 10 pour retrouver le mot encodé
//cout << enc <<endl;
/* DÉCRYPTAGE
*
**************/
l = floor(log(double(enc)) / log(255.0)) + 1; //Retrouver la longeur du mot
for (j=0;j<39;j++) cout << "--";
cout << endl;
cout <<"LONGEUR DU MOT : " << l << endl;
for (j=0;j<39;j++) cout << "--";
cout << endl;
long long d;
while (l > 0) {
d = enc / pow(255.0,(l-1));
enc = enc % (long long(pow(255.0,(l-1))));
cout << enc << endl;
cout << d << " " << char(d) << endl;
o << char(d);
l--;
}
s = o.str();
reverse(s.begin(),s.end());
cout << "MOT D"<<char(0x90)<<"CRYPT"<<char(0x90)<<" : " << s << endl;
for (j=0;j<39;j++) cout << "--";
cout << endl;
return 0;
}
------------------------------------------------------------------------------
b:98*1;u(n-1)+u(i)=98
o:111*255;u(n-1)+u(i)=28403
n:110*65025;u(n-1)+u(i)=7181153
j:106*16581375;u(n-1)+u(i)=1764806903
o:111*4228250625;u(n-1)+u(i)=471100626278
u:117*1078203909375;u(n-1)+u(i)=126620958023153
r:114*274941996890625;u(n-1)+u(i)=31470008603554403
------------------------------------------------------------------------------
MOT CRYPTÉ en base 10: 31470008603554403
------------------------------------------------------------------------------
------------------------------------------------------------------------------
LONGEUR DU MOT : 7
------------------------------------------------------------------------------
126620958023153
114 r
471100626278
117 u
1764806903
111 o
7181153
106 j
28403
110 n
98
111 o
0
98 b
MOT DÉCRYPTÉ : bonjour
------------------------------------------------------------------------------
Appuyez sur une touche pour continuer...
Ensuite, je me demandais comment faire disparaitre les blancs dans un un long texte crypté et faire idéalement qu'il soit + court que le texte initial en clair ?
Merci bien en tous cas pour votre aide.
@+
#16 Programmation » [C++] Caractéristiques de vol de la suite de Syracuse » 25-07-2009 10:58:50
- SébastienB
- Réponses : 0
Bonjour,
Voici mon programme pour calculer le temps de vol, le temps de vol en altitude et l'altitude maximale d'une suite de Syracuse:
using namespace std;
int main(){
int i = 0;
int u_0, u_i;
int u_n = 0;
int tpsVol = 0;
int tpsVolAlt = 0;
int altMax = 0;
cout << "SUITE DE SYRACUSE" << endl << "U0 ?"; cin >> u_0;
u_i = u_0 ;
while ( u_n != 1 ) {
if ( u_i % 2 == 0 )
u_i = u_i / 2;
else
u_i = u_i * 3 + 1;
if ( ( u_i <= u_0 ) && (i > 0) && (tpsVolAlt == 0) )
tpsVolAlt = i;
if ( altMax < u_i )
altMax = u_i;
u_n = u_i;
cout << u_n << " ";
i++;
}
cout << endl << "Temps de vol: " << i << endl;
cout << "Temps de vol en altitude: " << tpsVolAlt << endl;
cout << "Altitude maximale: " << altMax << endl;
return 0;
}
À + tard
SébastienB.
#17 Re : Café mathématique » Conjecture de Syracuse : discussion ouverte par Titus » 23-07-2009 21:20:23
Bonsoir,
Pas la peine de préciser que je ne lis pas le journal scientifique :) mais bon, comme ce sont les vacances (enfin pas pour moi) je voudrais savoir si on peut l'exprimer comme ceci avec du langage mathématique cette conjecture :
[tex]\begin{center}\underline{\textbf{CONJECTURE DE SYRACUSE}}\end{center}\bigskip\begin{equation}\textit{Conjecture de Syracuse} =\begin{cases}u_0 > 0\\u_{n+1} =\begin{cases}\frac{u_n}{2} & \text{Si $u_n$ est pair}\\u_n \times 3 + 1 & \text{Si $u_n$ est impair}\\ \end{cases}\\ (\forall u_0 \in \mathbb{N}) (\exists n \in \mathbb{N}) (u_n = 1)\\ \end{cases}\\ \end{equation}[/tex]
?
#18 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » L'illusion d'Hélène » 17-07-2009 21:25:58
Bonsoir,
Après avoir vu la suite de Syracuse sur votre super forum, j'ai voulu revoir bien evidemment aussi la suite de Fibonacci et de là je suis tombé sur le nombre d'or que je connaissais bien pour l'avoir à plusieurs reprises mis en pratique dans des maquettes en bois.
Si je peux me permettre, moi je trouve cela tout simplement épatant de constater à quel point tout est lié, particulièrement avec les mathématiques.
Maintenant, de là à trouver aussi un lien avec l'identité d' Euler ?
☺http://fr.wikipedia.org/wiki/Nombre_d'or
☺http://www.youtube.com/user/VeritySeeker
Merci.
@+
#19 Re : Entraide (supérieur) » Particularité d'une relation [Résolu] » 17-04-2009 07:04:46
Bonjour,
Merci pour cette précision.
@+
#20 Entraide (supérieur) » Particularité d'une relation [Résolu] » 16-04-2009 20:31:14
- SébastienB
- Réponses : 2
Bonjour,
Je recherche la particularité d'une relation cartésienne pour un exercice :
Soit [tex]E[/tex] un ensemble fini muni d'une relation d'équivalence [tex]\Re[/tex]. On numérote d'abord les classes d'équivalence de [tex]\Re[/tex], puis les éléments de [tex]E[/tex] en commençant par ceux de la première classe d'équivalence, puis par ceux de la deuxième, ainsi de suite jusqu'a la dernière. Avec cette façon de ranger les éléments de [tex]E[/tex], quelle est la particularité de la représentation cartésienne de [tex]\Re[/tex]. (comme exemple, prendre [tex]E = \big\{0,1,2,3,4,5,6,7\}[/tex] et [tex]x \Re y \Leftrightarrow x - y[/tex] est multiple de 3).
Ma représentation cartésienne du problème est :
[tex]\begin{tabular}{ccccccccc} &0&1&2&3&4&5&6&7\\ 0 & \blacksquare & \blacksquare & & \blacksquare & & & \blacksquare & \bigskip \\ 1 & \blacksquare & \blacksquare & \blacksquare & & \blacksquare & & &\blacksquare \bigskip \\ 2 & & \blacksquare & \blacksquare & \blacksquare & & \blacksquare & & \bigskip \\ 3 & \blacksquare & & \blacksquare & \blacksquare & \blacksquare & & \blacksquare & \bigskip \\ 4 & \bigskip & \blacksquare & & \blacksquare & \blacksquare & \blacksquare & & \blacksquare \end{tabular}[/tex]
[tex]\begin{tabular}{ccccccccc}5& \bigskip & & \blacksquare & & \blacksquare & \blacksquare&\blacksquare & \\ 6 & \blacksquare & & & \blacksquare & \bigskip & \blacksquare & \blacksquare & \blacksquare \\ 7 & \bigskip & \blacksquare & & & \blacksquare & & \blacksquare & \blacksquare \end{tabular}[/tex]
[tex]\bullet \Re \text{ est réflexive:}[/tex] Soit [tex]a[/tex] un élément quelconque de [tex]E. a - a = 0 = 3 \times 0 \text{, ainsi } (\forall a \in E)(a \Re a)\end{itemize}[/tex]
[tex]\bullet \Re \text{ est symétrique:}[/tex] Soient [tex]a[/tex] et [tex]b[/tex] deux éléments de [tex]E[/tex]. Supposons [tex]a \ \Re \ b [/tex], alors il existe [tex]p \in \mathbb{Z}[/tex] tel que [tex]b - a = 3p[/tex], en inversant les termes par rapport au signe égal, on obtient [tex]a - b = -3p = 3 \times (-p) [/tex] et donc [tex]b \ \Re \ a[/tex]. Ainsi, [tex](\forall a \in E)(\forall b \in E) \big((a \ \Re \ b) \Rightarrow (b \ \Re \ a)\big)[/tex]
[tex]\bullet \Re \text{ est transitive:}[/tex] Soient [tex]a; b[/tex] et [tex]c[/tex] trois éléments de [tex]E[/tex] , supposons que [tex]a \ \Re \ b[/tex] et [tex]b \ \Re \ c[/tex] alors il existe [tex]p[/tex] et [tex]q[/tex] deux entiers relatifs tels que [tex]b - a = 3p[/tex] et [tex]c - b= 3q[/tex], en ajoutant membre à membre ces deux égalités, on obtient [tex]c-a = 3(p + q)[/tex] et donc [tex]a \ \Re \ c[/tex]. Ainsi, on a démontré que :
[tex](\forall a \in E)(\forall b \in E)(\forall c \in E)\big([(a \Re b)\land (b \Re c)] \Rightarrow (a \Re c)\big)[/tex]
On peut donc ranger les éléments de [tex]E[/tex] dans différents sous ensembles appelés classes d'équivalences, dont ils sont en relation avec un des éléments: [tex]\frac{E}{\Re} = \big\{\bar{0};\bar{1};\bar{2}\big\}[/tex]
Mais je ne suis pas sur d'avoir bien compris cette façon de numéroter les éléments dans les classes d'équivalence, dans cet énonçé, c'est une identification relative (le 1er élément de la 1ere classe, le 2nd élément de la 1ere classe, le 1er élément de la 2e classe, le 2nd élément de la 2ere classe, etc.) ?
Que faut il comprendre et quelle est la particularité de cette relation à part qu'elle est parfaitement réflexive et symétrique ?
Pouvez vous me donner votre point de vue s'il vous plaît ?
PS: en tant que fan du [tex]\LaTeX[/tex] je souhaiterai pouvoir en écrire un peu + entre deux balises [ tex]. De plus, j'ajouterai que ce serait vraiment génial pour votre forum si on pouvait poster du code PSTricks comme cela on pourrait y voir des dessins géométriques de bonne qualité. Bon sur ce je vous souhaite une bonne soirée.
#21 Re : Entraide (supérieur) » Relations et classes d'equivalences [Résolu] » 15-04-2009 16:46:00
Merci pour cette réponse rapide.
À bientôt
#22 Re : Entraide (supérieur) » Intégrale impropre [Résolu] » 15-04-2009 11:12:52
Bonjour,
c'est une extension de l'intégrale usuelle, définie par une forme de passage à la limite dans des intégrales.
http://fr.wikipedia.org/wiki/Intégrale_généralisée
d'autres personnes auront sûrement de meilleures explications
@+
#23 Entraide (supérieur) » Relations et classes d'equivalences [Résolu] » 15-04-2009 11:09:45
- SébastienB
- Réponses : 2
Bonjour,
J'ai quelques exercices de démonstrations de relations à faire. En faisant un diagramme cartésien , pas de pb j'ai bien compris et je vois bien si la relation est symétrique, antisymétrique ou transitive; mais pour le démontrer avec du langage mathématique c'est une autre histoire pr moi.
Pouvez vous me filer un coup de pouce s'il vous plait ?
1.)[tex]E = \mathbb{R}, \ x \ \Re \ y \ \Leftrightarrow \ x = - y[/tex]
Je dirai que la valeur absolue de y correspond à celle de x donc la relation est réflexive, symétrique et antisymétrique car elle se trouve sur la diagonale du diagrame cartésien.
2.)[tex]E = \mathbb{R}, \ x \ \Re \ y \ \Leftrightarrow \ (\cos{x})^2 + (\sin{y})^2 = 1[/tex]
C'est comme au 1 car [tex]\forall x \in \mathds{R}, (\cos x)^2 + (\sin x)^2 = 1[/tex]
3.)[tex]E = \mathbb{N}, \ x \ \Re \ y \ \Leftrightarrow [/tex] il existe p et q deux nombres supérieurs ou égaux à 1 tels que [tex]y = p \times x^q[/tex]
Si p et q valent 1, alors y = x et c'est réflexif, sinon c'est antisymétrique et je ne pense pas que ce soit transitif car je ne vois pas d'application g (ni de f d'ailleurs) telle que [tex]g \circ f(x) = y[/tex], en effet, si x vaut 2 et p vaut 2 et q vaut 1, on a y = 4 et si x vaut 1 et p vaut 3 et q vaut 1, on a y = 3 et dans ce cas là on devrait avoir
x = 1 en relation avec y = 4 pour que ce soit transitif, or ce n'est pas le cas.
Mais j'ai un doute sur la validité de ma démonstyration alors merci de votre aide en tt cas.
4.)Soit [tex]E = \mathbb{Z}[/tex] muni de la relation [tex]\Re[/tex] telle [tex]x \ \Re \ y \ \text{si} \ x+y \ \text{est pair}[/tex]. Montrer que [tex]\Re[/tex] est une relation d'équivalence et donner les classes d'équivalence de [tex]\Re[/tex]
Pour avoir une relation d'équivalence, il faut qu'elle soit réflexive, symétrique et transitive.
C'est réflexif car par exemple [tex]2 \ \Re \ 2[/tex], symétrique car [tex]2 \ \Re \ 3 \ \text{et} \ 3 \ \Re \ 2[/tex] et transitif car on a bien 5 en relation avec 3 et 3 en relation avec 5 qui donne que le nombre 10 qui est pair est bien l'addition de 5 en relation avec 5.
par exemple pour l'ensemble [tex]E = \{-2,2,3,5\} [/tex]
Je dirai que les classes d'équivalence sont [tex]\frac{E}{\Re} = \big\{\bar{-2},\bar{3}\big\}[/tex]
Merci bien d'avance, si vous pouver m'en dire plus.
@+
#24 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » La seconde inconnue ... » 11-04-2009 17:38:26
Pigé!
C'est très amusant je suis d'accord, et c'est facile en fait quand on peut éliminer un couple de solution sur deux possible.
J'aimerai bien voir la démonstration avec 196 et 28 par exemple pour voir si pour moi c'est pareil.
Merci =-)
#25 Re : Enigmes, casse-têtes, curiosités et autres bizarreries » La seconde inconnue ... » 11-04-2009 09:42:31
Bonjour,
Je n'ai jamais vu cette énigme mais en faisant abstraction des commentaires, je ferai comme ceci pour trouver [tex]\text{deux entiers} \ x \ \text{et} \ y \ \text{dont la somme} \ S \ \text{et le produit} \ P \ \text{sont connus}[/tex] :
[tex]x + y = S \ \text{et} \ x \times y = P[/tex]
[tex]\begin{align}(x+y)^2 - (x-y)^2 &= 4xy \\ (S)^2 - (x-y)^2 &= 4P \\ (x-y)^2 &= S^2 - 4P \\ x-y &= \sqrt{(S^2 - 4P)}\end{align}[/tex]
On obtient ensuite donc un système d'équation à deux inconnues que l'on pourra résoudre au choix par substitution ou alors par combinaison linéaire :
[tex]\begin{cases}x+y &= S\\x-y &= \sqrt{(S^2 - 4P)}\end{cases}[/tex]
[tex]\begin{align}2x &= S+\sqrt{(S^2 - 4P)}\\x &= \frac{S+\sqrt{(S^2 - 4P)}}{2}\\y &= S - \frac{(S+\sqrt{(S^2 - 4P)})}{2}\end{align}[/tex]
Connaissant [tex]4 \le S \le 200 \ \text{et} \ 4 \le P \le 10000[/tex], il est probable que ça demande des calculs avec des grands nombres qui prendraient probablement plus de quelques secondes...
Ps : Cette équation [tex](x+y)^2 - (x-y)^2 = 4xy[/tex] aussi connue des Grecs que j'ai trouvé sur Internet
ressemble à l'identité de Diophante mais ce n'est pas tout a fait pareil. Est ce que vous la connaissez aussi ?
@+