Loading [MathJax]/jax/output/HTML-CSS/jax.js
Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu

20×20 tablodaki komşu 4 sayının çarpımının en büyük değeri kaçtır?

0 beğenilme 0 beğenilmeme
943 kez görüntülendi

Project Euler'den problem 11 şu şekildedir: 

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

 

Kırmızı ile renklendirilmiş dört sayı komşudur: Bunların çarpımı 26⋅63⋅78⋅14=1788696 dır. Yukarı, aşağı, sağ, sol veya köşegen yönünde komşu olan dört sayının çarpımı en fazla kaçtır?

 

Not: Soruların çözümlerinin kod yazarak yapılması beklenmektedir. Ben de daha sonra python çözümümü paylaşacağım.

 

 

Veri Bilimi kategorisinde (2.6k puan) tarafından  | 943 kez görüntülendi
emin olmak icin soruyorum sadece 45 dereceli diagonellere bakacagim degil mi ? At gibi hareketleri diagonelden saymiyoruz ?
(1.6k puan) tarafından 
At'ın hareketi gibi olmuyor. Aynı köşegen üzerindeki komşu olan sayılar olur. Ana köşegenlerden herhangi birine paralel olan dört doğrusal komşu sayı da olabilir. Örnekteki kırmızı renkli sayılar gibi. Yukarı-aşağı, sağ-sol yönler ve diğer köşegen yönü de unutulmamalı tabii.
(2.6k puan) tarafından 
tarafından düzenlendi

3 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap

Mathematica ile soyle yapabiliriz.

dikeyYatay[mat_] := Flatten[Partition[#, 4, 1] & /@ mat, 1]
kosegenAl[mat_] := dikeyYatay@(Diagonal[mat, #] & /@ Range[-16, 16])
Times @@@  Flatten[Through[{dikeyYatay, kosegenAl}[#]] & /@ {mat, Transpose@mat}, 2] // Max

Test etmek icin su matrisi kullandim

mat=(123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400)

 

Cevabin 397∗398∗399∗400=25217757600 oldugu asikar ve kod bu cevabi veriyor.

(2.9k puan) tarafından 
tarafından seçilmiş
1 beğenilme 0 beğenilmeme

Julia dilinde soyle hizli brute force bir cozumum oldu. Dogrulugundan yuzde yuz emin degilim ama paylasayim

julia> a = [ 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

       49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

       81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

       52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

       22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

       24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

       32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

       67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

       24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

       21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

       78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

       16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

       86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

       19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

       04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

       88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

       04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

       20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

       20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

       01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48]
20×20 Matrix{Int64}:
  8   2  22  97  38  15   0  40   0  75   4   5   7  78  52  12  50  77  91   8
 49  49  99  40  17  81  18  57  60  87  17  40  98  43  69  48   4  56  62   0
 81  49  31  73  55  79  14  29  93  71  40  67  53  88  30   3  49  13  36  65
 52  70  95  23   4  60  11  42  69  24  68  56   1  32  56  71  37   2  36  91
 22  31  16  71  51  67  63  89  41  92  36  54  22  40  40  28  66  33  13  80
 24  47  32  60  99   3  45   2  44  75  33  53  78  36  84  20  35  17  12  50
 32  98  81  28  64  23  67  10  26  38  40  67  59  54  70  66  18  38  64  70
 67  26  20  68   2  62  12  20  95  63  94  39  63   8  40  91  66  49  94  21
 24  55  58   5  66  73  99  26  97  17  78  78  96  83  14  88  34  89  63  72
 21  36  23   9  75   0  76  44  20  45  35  14   0  61  33  97  34  31  33  95
 78  17  53  28  22  75  31  67  15  94   3  80   4  62  16  14   9  53  56  92
 16  39   5  42  96  35  31  47  55  58  88  24   0  17  54  24  36  29  85  57
 86  56   0  48  35  71  89   7   5  44  44  37  44  60  21  58  51  54  17  58
 19  80  81  68   5  94  47  69  28  73  92  13  86  52  17  77   4  89  55  40
  4  52   8  83  97  35  99  16   7  97  57  32  16  26  26  79  33  27  98  66
 88  36  68  87  57  62  20  72   3  46  33  67  46  55  12  32  63  93  53  69
  4  42  16  73  38  25  39  11  24  94  72  18   8  46  29  32  40  62  76  36
 20  69  36  41  72  30  23  88  34  62  99  69  82  67  59  85  74   4  36  16
 20  73  35  29  78  31  90   1  74  31  49  71  48  86  81  16  23  57   5  54
  1  70  54  71  83  51  54  69  16  92  33  48  61  43  52   1  89  19  67  48

julia> function candidates(a)  ## BU cozum eksik/hatali 4 kisiye bakmak yerine 5 kisiye bakiyor
       s = Set()
       for i ∈ 1:16
           for j ∈ 1:16
               ret = a[i:i+4,j:j+4]
               for k ∈ 1:4
                   push!(s,ret[k,:])
                   push!(s,ret[:,k])
               end
               push!(s,diag(ret))
               push!(s,antidiag(ret))
           end
       end
       s
       end
candidates (generic function with 1 method)


julia> function candidates(a,n)  ## BU cozum eksik/hatali 4 kisiye bakmak yerine 5 kisiye bakiyor
       n = n-1
       s = Set()
       for i ∈ 1:16
           for j ∈ 1:16
               ret = a[i:i+n,j:j+n]
               for k ∈ 1:n
                   push!(s,ret[k,:])
                   push!(s,ret[:,k])
               end
               push!(s,diag(ret))
               push!(s,antidiag(ret))
           end
       end
       s
       end
candidates (generic function with 1 method)

julia> antidiag(x) = [x[i,end - i+1] for i in 1:size(x)[1] ]
antidiag (generic function with 1 method)

julia> candidates(a,4) .|> prod |> maximum
3318231678

 

(1.6k puan) tarafından 
tarafından düzenlendi
Doğru cevap 3318231678 den daha farklı bir sayıdır. 1004=108 olduğundan, yanıt en fazla 8 basamaklı olabilir.
(2.6k puan) tarafından 
70600674 bu mu acaba buysa cok sacma bir hata yapmisim
(1.6k puan) tarafından 
Tebrikler @eloi doğru yanıt 70600674
(2.6k puan) tarafından 
yukaridaki algoritma calisiyor sadece 4 tane yerine 5 tane komsuya bakiyordum
(1.6k puan) tarafından 
@eloi , yanıttaki kodunuzu güncelleyebilirseniz sevinirim. (Özel mesaj yazdım ama görünmedi belki.) Teşekkürler.
(2.6k puan) tarafından 
pardon yeni zamanim olabildi
(1.6k puan) tarafından 
0 beğenilme 0 beğenilmeme 
num = '''
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
'''

# Önce string türündeki 400 sayıyı liste1'te tutuyoruz. liste2 isimli liste ile 20x20 türünde ve elemanları integer (tam sayı) türünde bir matris (veya listelerin listesini) oluşturuyoruz.

liste1 = num.split()
liste2 = []
for i in range(0,20):
  liste3 = []
  for j in range(0,20):
    liste3.append(int(liste1[20*i+j]))
  liste2.append(liste3)

# Yatay yönde komşu olan 4 sayının çarpımını prod isimli listede tutuyoruz.
prod = []
for i in range(0, 20):
    for j in range(0,17):
        p = liste2[i][j]*liste2[i][j+1]*liste2[i][j+2]*liste2[i][j+3]
        prod.append(p)


# Dikey yönde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,20):
        p = liste2[i][j]*liste2[i+1][j]*liste2[i+2][j]*liste2[i+3][j]
        prod.append(p)

# Esas köşegen yönünde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,17):
        p = liste2[i][j]*liste2[i+1][j+1]*liste2[i+2][j+2]*liste2[i+3][j+3]
        prod.append(p)

# İkinci köşegen yönünde komşu olan 4 sayının çarpımını prod isimli listeye ekliyoruz. 
for i in range(0,17):
    for j in range(0,17):
        p = liste2[i+3][j]*liste2[i+2][j+1]*liste2[i+1][j+2]*liste2[i][j+3]
        prod.append(p)

# Oluşabilecek tüm dörtlü çarpımlar prod isimli listededir. Bu listenin en büyük elemanını seçerek çözümümüzü tamamlarız.

print(max(prod))

 

(2.6k puan) tarafından 

İlgili sorular

20,301 soru
21,851 cevap
73,562 yorum
2,790,901 kullanıcı