Feb. 28th, 2012

the_grue: (Default)
Легкая, конечно, но не настолько, как кажется на первый взгляд. Приведите реализацию следующего интерфейса (здесь код на Scala, но ответы принимаются на любом языке):
trait Matrix[T] {
  // returns the element at i,j
  def at(i:Int, j:Int): T

  // returns the number of rows and columns in this matrix
  def size(): (Int,Int)

  // returns a new matrix, whose (i,j)'th element is the (d*i+r, d*j+c)'th
  // element of this matrix (d>=1, r,c>=0)
  def divide(d:Int, r:Int, c:Int): Matrix[T]
}

object Matrix {
  def make[T](arr: Array[Array[T]]) = ???
}


На всякий случай объясню словами: надо написать враппер для двухмерного массива, который
1) умел бы выполнять все обычные операции над массивом, кроме модификации ячеек. Известно, что массив, над которым конструируется враппер, никогда не изменится (immutable).
2) умел бы возвращать подматрицу, содержащую строки исходной матрицы с индексами вида d*i+r и её столбцы с индексами вида d*j+c. Визуально это можно представить так: мы разбиваем нашу матрицу на квадраты размером d*d ячеек (смещенные на r строк вниз и c столбцов вправо) и возвращаем новую матрицу, содержащую только верхний левый элемент каждого из квадратов.

Требования к сложности времени выполнения: O(1) для всех операций над всеми объектами типа Matrix.

Ответ: dHJhaXQgTWF0cml4W1RdIHsKICAvLyByZXR1cm5zIHRoZSBlbGVtZW50IGF0IGksagogIGRlZiBhdChpOkludCwgajpJbnQpOiBUCgogIC8vIHJldHVybnMgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIGluIHRoaXMgbWF0cml4CiAgZGVmIHNpemUoKTogKEludCxJbnQpCgogIC8vIHJldHVybnMgYSBuZXcgbWF0cml4LCB3aG9zZSAoaSxqKSd0aCBlbGVtZW50IGlzIHRoZSAoZCppK3IsIGQqaitjKSd0aCBlbGVtZW50IG9mCiAgLy8gdGhpcyBtYXRyaXggKGQ+PTEsIHIsYz49MCkKICBkZWYgZGl2aWRlKGQ6SW50LCByOkludCwgYzpJbnQpOiBNYXRyaXhbVF0KfQoKb2JqZWN0IE1hdHJpeCB7CiAgZGVmIG1ha2VbVF0oYXJyOiBBcnJheVtBcnJheVtUXV0pID0gTWF0cml4SShhcnIsIDEsIDAsIDApCn0KCgoKY2FzZSBjbGFzcyBNYXRyaXhJW1RdKG06QXJyYXlbQXJyYXlbVF1dLCBkaXZpc29yOkludCwgb2Zmc2V0cjpJbnQsIG9mZnNldGM6SW50KSBleHRlbmRzIE1hdHJpeFtUXSB7CiAgZGVmIGF0KGk6SW50LCBqOkludCkgPSBtKGkqZGl2aXNvcitvZmZzZXRyKShqKmRpdmlzb3Irb2Zmc2V0YykKICBkZWYgYXBwbHkoaTpJbnQsIGo6SW50KSA9IGF0KGksaikKICBkZWYgc2l6ZSgpID0gKHN6KG0sIG9mZnNldHIpLCAgc3oobSgwKSwgb2Zmc2V0YykpCiAgZGVmIGRpdmlkZShkOkludCwgb2ZmcjpJbnQsIG9mZmM6SW50KSA9IE1hdHJpeEkobSwgZGl2aXNvcipkLAoJCQkJCQkJCQkJCQkgIGRpdmlzb3Iqb2ZmciArIG9mZnNldHIsCgkJCQkJCQkJCQkJCSAgZGl2aXNvcipvZmZjICsgb2Zmc2V0YykKICBwcml2YXRlIGRlZiBzeltWXShtOkFycmF5W1ZdLCBvZmZzZXQ6SW50KSA9IChtLmxlbmd0aC1vZmZzZXQrZGl2aXNvci0xKS9kaXZpc29yCn0KCgp2YWwgYSA9IE1hdHJpeC5tYWtlKEFycmF5LmZyb21GdW5jdGlvbigoaTpJbnQsajpJbnQpID0+ICIiICsgaSArICIsIiArIGopICgxMDAsMTAwKSkK
Page generated Jul. 25th, 2017 08:39 pm
Powered by Dreamwidth Studios