Project Euler – 04

Uzun zamandır Project Euler’a bakmıyordum. Son yazımı yayınlayınca blogun sağ kısmında profilimin banner’ını görünce kendi kendime yahu bayadır girmiyorsun şu siteye. müsait olunca gir de sıradaki problemi çöz dedim. Gerçi sırayla çözmek zorunda da değilsiniz, project euler’ı bilenler bilir. Fakat sırayla çözmeyi tercih ediyorum ben. 4. soru biraz uğraştırdı beni, zor olduğu için değil gerçi çeşitli faktörlerden dolayı dikkatimi yeterince veremedim bugün. Ama yine bahane sayılmaz bu, bugün biraz çucalladık, zaten birazdan tam çözümünü veren kodu da vermeyeceğim size. Aslında doğru çözümü veriyor fakat kodun doğasında ufak bir “assumption based bug” var.

Bunu açıklamadan önce 4. problemi verelim hemen:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99. Find the largest palindrome made from the product of two 3-digit numbers.

Şimdi buradaki bug’ı açıklıyorum: Benim burada uyguladığım palindrom oluşturma mantığı iç içe 2 adet for döngüsü ile palindrom sayıların çarpanlarını oluşturmak ve döngünün içerisindeki bir takım işlemlerle bu çarpanlarını çarpımının palindrome olup olmadığını kontrol etmek. Şimdi, bu işlem sonucunda n tane palindrom elde ettiğimizi varsayalım. her palindromun A ve B isimli çarpanları olsun. Düz mantık kodu çalıştırdığımızda elde ettiğimiz son çarpımın en büyük olmasını öne sürüyor. Fakat gerçekte n. palindrom olan sayı 580085 ve çarpanları ise 995 ve 583 olmasına rağmen (n-2) palindrom 906609 ve çarpanları ise 993 ve 913.

Bizim (ne ara 1. tekil şahıstan 1. çoğul şahısa geçtim bende bilmiyorum😛😀 ) burada iç içe döngü kullanırken istemeden neden olduğumuz durum ise ancak şöyle açıklanabiliyor:  1. çarpan artırılırken yeni bir palindrom oluşturmak için bir önceki çarpan kombinasyonlarına göre büyük bir fark ile geride kalan palindrom oluşma olasılığı bazen bu durumda oluşabilecek tek palindrom olma olasılığına sahiptir. Çünkü 1. çarpanın artmasına bağlı olarak 2. çarpanın çarpımı palindrom yapacak olan muhtemel değeri bir önceki kombinasyonlara göre büyük fark ile küçük olabiliyor.

Ben sonucu kendi outputlarımda gördüğüm için daha fazla kodu düzeltme ihtiyacı hissetmiyor ve aşağıdaki haliyle bırakıyorum. Fakat düzeltmek isteyen arkadaşlara önerim res ve product değerlerini bir kez daha string’den int tipine değiştirmeleri ve res değerini gelen her yeni palindrom product’ı ile karşılaştırıp res içerisinde maksimum sayı değerini tutmaları.

Neyse, işte kod:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CS_11_project_Euler_problem_4
{
class Program
{

static void Main(string[] args)
{
int x, y;
string product="0" , res="0";

for (x = 100; x <= 999; x++)
{
for (y = 100; y <= 999; y++)
{
product = Convert.ToString(x*y);

if (product == new String(product.Reverse().ToArray()))
{

res = product;

Console.WriteLine("X=" + x + " Y=" + y + " Polindrome is: " + res);
}

else { continue; }
}
}
}
}
}

İşte bu da ekran alıntısı:

1 Yorum

Filed under Project Euler

One response to “Project Euler – 04

  1. serhat

    merhaba timur bey aşağıda yazdığım Project Euler problemi hakkında yardım edebilirmisiniz?

    If you start from the top and move downwards to an adjecent number as in below, the maximum sum of the numbers from top to bottom is 24. You are only allowed to walk downwards and diagonally and only over non prime numbers!
    1
    8 4
    2 6 9
    8 5 9 3
    1 + 8 + 6 + 9 = 24. As you see 1, 8, 6, 9 are all not prime numbers
    and walking over these yields the maximum sum.
    a-) What is maximum sum if you start from top to bottom from below data:
    215
    193 124
    117 237 442
    218 935 347 235
    320 804 522 417 345
    229 601 723 835 133 124
    248 202 277 433 207 263 257
    359 464 504 528 516 716 871 182
    461 441 426 656 863 560 380 171 923
    381 348 573 533 447 632 387 176 975 449
    223 711 445 645 245 543 931 532 937 541 444
    330 131 333 928 377 733 017 778 839 168 197 197
    131 171 522 137 217 224 291 413 528 520 227 229 928
    223 626 034 683 839 53 627 310 713 116 629 817 410 121
    924 622 911 233 325 139 721 218 253 223 528 233 230 124 233

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s