SORU
4 Mart 2013, PAZARTESİ


Zig-zag N x N bir dizi tarama

Basit bir dizi var. Dizi uzunluğu her zaman bir tam sayı kare kökü vardır. Yani 16, 25, 36 vb.

$array = array('1', '2', '3', '4' ... '25');

Ne yapmam, hatta bir tarafı olan bir blok gibi görünüyor, böylece HTML ile dizi düzenlemek.

Ne yapmak istiyorum, biraz unsurları, böylece ne zaman bitirirsem JSON kodlanmış dizi DV olacaktır yineleme dizisi, fade akımı engeller, ve çok isterdim bir nevi dalga animasyon. Bu dizi böyle sıralamak istiyorum

Sıralanmış dizi benim gibi görünecekti

$sorted = array('1', '6', '2', '3', '7', '11', '16, '12' .. '25');

Bunu yapmak için..? bir yolu yok. Teşekkürler

CEVAP
5 Mart 2013, Salı


Soru çok hoş. İşte bir analiz ve bir algoritma.

Bir anahtar avantajı kullanarak bu algoritma o zaman bu iş Tamam kullanarak basit tamsayı hesaplama; hiçbir "eğer" ifadeleri ve bu nedenle dallar yok, yani olsa derlenmiş, ki çok hızlı bir şekilde yürütmek için bile çok büyük değerler n. Bu da kolayca birden çok işlemci arasında iş bölmek parallelized olabilir anlamına gelirçokn büyük değerler.

Düşünün bir 8x8 ızgara (burada, giriş teknik olarak n = 64, ama kullanım kolaylığı için formüller aşağıda olacağım kullanarak n = 8) aşağıdaki Bu zikzak desen gibi yani (0-endeksli satır ve sütun ekseni):

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1    3    4   10   11   21   22   36
[ 1]   2    5    9   12   20   23   35   37
[ 2]   6    8   13   19   24   34   38   49
[ 3]   7   14   18   25   33   39   48   50
[ 4]  15   17   26   32   40   47   51   58
[ 5]  16   27   31   41   46   52   57   59
[ 6]  28   30   42   45   53   56   60   63
[ 7]  29   43   44   54   55   61   62   64

İlk önce sol alt (0,7) üst sağ (7,0) çapraz ikiye ızgara neredeyse-aynalı bileşenleri: bölen dikkat edin

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1    3    4   10   11   21   22   36
[ 1]   2    5    9   12   20   23   35
[ 2]   6    8   13   19   24   34
[ 3]   7   14   18   25   33
[ 4]  15   17   26   32
[ 5]  16   27   31
[ 6]  28  30
[ 7]  29

ve

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]                                     36
[ 1]                                35   37
[ 2]                           34   38   49
[ 3]                      33   39   48   50
[ 4]                 32   40   47   51   58
[ 5]            31   41   46   52   57   59
[ 6]       30   42   45   53   56   60   63
[ 7]   29  43   44   54   55   61   62   64

Alt-sağ üst-sol yansıtılmış ve artı 1 kare (Bu durumda 65) çıkartılır.

Eğer biz hesaplayabilir sol üst kısmı, sonra alt kısmı doğru olabilir hesapladığı alıyorum Kare artı 1 (n * n 1) ve çıkarma değeri de ters koordinatları (value(n - x - 1, n - y - 1)).

Örnek olarak, sağ-alt kısmında koordinatları rasgele bir çift düşünün, diyelim ki (6,3), 48 değerine sahip. Bu formül şu o (8 * 8 1) - value(8 - 6 - 1, 8 - 3 - 1), 65 - value(1, 4) basitleştirilmiş için çalışmaya devam eder. Sol üst kısmına bakarak, (1,4) değeri 17. Ve 65 - 17 == 48.

Ama hala sol üst kısmını hesaplamak gerekir. Bu da daha fazla üst üste gelen iki bileşenleri, sayılar kafa olarak yukarı doğru artan bir bileşen içine alt bölünmüş olabilir

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]        3        10        21        36
[ 1]   2         9        20        35
[ 2]        8        19        34
[ 3]   7        18        33
[ 4]       17        32
[ 5]  16        31
[ 6]       30
[ 7]  29

Ve numaraları ile bir bileşen kafa olarak artan Aşağı-Sol:

     [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7]
[ 0]   1         4        11        22     
[ 1]        5        12        23     
[ 2]   6        13        24     
[ 3]       14        25     
[ 4]  15        26     
[ 5]       27     
[ 6]  28    
[ 7]    

Eski de toplamı koordinatları numaralarını (x y) garip olarak tanımlanabilir, ve ikincisi toplamı koordinatları nereye numaraları olarak tanımlanır.

Şimdi, temel fikir burada üçgenler çizim olduğunu, bu yüzden, doğal olarak, bu Triangular Numbers önemli rol oynar. Sıra Üçgen sayısı: 1, 3, 6, 10, 15, 21, 28, 36, ...

Gördüğünüz gibi, tek topla bileşeni, diğer her Üçgen sayısı ile başlayan 3 açılan ilk satır (3, 10, 21, 36), ve hatta-toplam bileşen, diğer her Üçgen sayısı ile başlayan 1 görünür ilk sütunda (1, 6, 15, 28).

Özellikle, belirli bir çifti (x,0) veya (0,y) karşılık gelen Üçgen sayısı Üçgen koordinat(x 1) veya üçgen(y 1).

Ve grafiğin geri kalanını kademeli olarak belirli satır veya sütun sayısını çıkararak eşdeğer veya çapraz aşağı yukarı bu üçgensel sayılar, den çıkararak hesaplanabilir.

Bu bir notdiyagonalresmen koordinatları belirli bir miktar ile tüm hücre kümesi olarak tanımlanabilir. Örneğin, çapraz toplamı 3 koordinat koordinatlar(0,3)var, (1,2), (2,1), ve (3,0). Böylece tek bir numara her diyagonal tanımlar, ve bu sayı da başlayan Üçgen sayısını belirlemek için kullanılır.

Basit bir kontrol yani, tek topla bileşeni hesaplamak için formül basit:"

triangle(x   y   1) - y

Ve hatta-toplam bileşeni hesaplamak için formül basit:"

triangle(x   y   1) - x

Ve üçgen sayılar için iyi bilinen bir formülü de basittir:

triangle(n) = (n * (n   1)) / 2

Yani, algoritma

  1. Başlatma n giriş Karekök içinde bulunduğu n x n bir dizi, boyutu.
  2. Hatta toplanan bu dizinler için koordinatları hesaplamak sol üst kısmı. Bu iç içe iki döngü, bir tarafından gerçekleştirilebilir dış döngü "y gitmekten 0-n - 1" ve bir iç döngü "x gitmekten y % 2 y adım 2" (sınırlama x, y, mevcut, biz sadece bak sol üst kısmını istediğiniz gibi, Ve ile başlayan y % 2 ve içeri adım 2 Biz sadece bu bile toplanır koordinatları). Döngü dizinleri formüle sonuçları almak için yukarıdaki takılabilir. value[x, y] = triangle(x y 1) - x.
  3. Tek toplandığı için dizinler hesaplamak sol üst kısmı koordinatları. Bu yapılabilir iç döngü dışında benzer döngüler olurdu "x y %2 1 2 adım", tek tek toplanır koordinatları almak için.. y value[x, y] = triangle(x y 1) - y.
  4. Hesaplamak bu yazı ilk bölümünde açıklandığı gibi n * n 1 basit çıkarma tarafından sağ-alt bölümü için dizin. Bu iç içe iki döngü tersten (ve sadece sağ alt kısmı için dış bir iç sınırlayıcı) sayma ile yapılabilir. value[x, y] = (n * n 1) - value[n - x - 1, n - y - 1].
  5. Dümdüz ızgara içine bir dizi (sıraya tüm satırlar) ve ardından dönüştürmek verilen giriş (boyutu n * n) çıkışını kullanarak sayıları oluşturulan kılavuz olarak yeni endeksleri.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Android Authority

    Android Auth

    3 NİSAN 2011
  • Microsoft Help & Training Videos

    Microsoft He

    31 Mart 2009
  • TeachMeComputer

    TeachMeCompu

    31 EKİM 2009