АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Бид мөр, багана, диоганалийн нийлбэр нь тэнцүү байх [1..n^2] завсраас утгаа авах ялгаатай элементүүдээс

тогтсон n x n  хэмжээтэй хүснэгтийг шидэт квадрат гэж нэрлэдэг.

Тэгвэл чамд [1..9] завсраас утгаа авах 3x3 хэмжээтэй S матриц (хүснэгт) өгөгдөв.

Хүснэгтийн [1..9] завсрын ямар нэг a-тоог ямар нэгэн b-тоо руу хувиргахад  |a-b| үнэ төлөх шаардлагатай.

Тэгвэл өгөгдсөн S матрицыг шидэт матриц болгох хамгийн бага үнэлгээг ол. 

Үүсэх шидэт квадрат нь [1..9] завсарт багтах ялгаатай элементүүдээс тогтох ёстой.

Шидэт квадрат болгоход шаардагдах хамгийн бага үнэлгээг нэг мөрөнд хэвлэнэ үү.

Тухайлбал жишээ болгох дараах матрицыг авч үзье.

5 3 4

1 5 8

6 4 2

Бид өгөгдсөн матрицыг дараах шидэт матриц руу хөрвүүлсэн гэж бодьё.

8 3 4

1 5 9

6 7 2

Тэгвэл бид энд |5-8|+|8-9|+|4-7|=7 гэсэн үнээр хөрвүүлнэ.

Оролт

Мөр бүр нь зайгаар тусгаарлагдсан 3 тооноос бүрдэх 3 мөр бүхий S матриц өгөгдөнө.

Хязгаарлалт

 S[i][j] нь [1..9] завсарт харьяалагдана.

Гаралт

Шидэт квадрат руу хувиргах хамгийн бага үнийг  (үнэлгээ) хэвлэнэ.

Оролт 0

4 9 2

3 5 7

8 1 5

Гаралт 1

 1

Тайлбар 1

Хүснэгтийн баруун доод талын 5 гэсэн утгыг 6 болгоход шидэт квадрат үүсэх учир |5-6|=1 үнэлгээгээр шидэт квадрат болгож байна.

Оролт 1

4 8 2

4 5 7

6 1 6

Гаралт 1

4

Тайлбар 2

S матрицын индексийг 0-ээс эхлэн дугаарлагдсан гэж үзвэл:

• S[0][1] элементийг  9 болгоход |8-9|=1
• S[1][0] элементийг  3 болгоход |3-4|=1
• S[2][0] элементийг  8 болгоход |8-6|=2 буюу

Нийт 1+1+2=4 гэсэн үнээр хувиргана.

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх