SORU
16 Temmuz 2010, Cuma


'örtüşme için?iki tam sayı aralığı test etmek için en etkili yolu nedir

Verilen şey dahil iki tam sayı aralığı [x1:x2] [y1:y2], nerede x1 <= x2 ve y1 <= y2, en verimli şekilde test edip bir üst üste iki aralıkları?

Basit bir uygulama aşağıdaki gibidir:

bool testOverlap(int x1, int x2, int y1, int y2) {
  return (x1 >= y1 && x1 <= y2) ||
         (x2 >= y1 && x2 <= y2) ||
         (y1 >= x1 && y1 <= x2) ||
         (y2 >= x1 && y2 <= x2);
}

Ama bu hesaplamak için daha etkili yollar vardır.

Hangi yöntem en az operasyonlar açısından en verimli olurdu.

CEVAP
16 Temmuz 2010, Cuma


Bunun için çakışan aralıklar için ne anlama geliyor? Orada her iki aralık içinde bir dizi C var demektir, yani

x1 <= C <= x2

ve

y1 <= C <= y2

Eğer aralıkları iyi biçimlendirilmiş olduğunu varsaymak izin varsa şimdi, x1 <;= x2 ve y1 <= y2) sonra test için yeterlidir

x1 <= y2 && y1 <= x2

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

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Leigh Momii

    Leigh Momii

    10 Mayıs 2006
  • Vintendo Power

    Vintendo Pow

    2 Ocak 2007
  • Within Temptation

    Within Tempt

    18 EYLÜL 2006