История изменений
Исправление
Legioner,
(текущая версия)
:
Без оптимизации так: считаем сумму всех элементов. S = sum_x_y xy[j] выбираем число от 0 до S - 1. t := random [0, S) Дальше псевдокод:
for i <- 0 .. 1000
for j <- 0 .. 1000
t := t - xy[i][j];
if t < 0
return (i, j)
Чтобы оптимизировать, надо хранить суммы по строкам. Дальше - сначала находим строку, потом в ней находим столбец.
Возможно целочисленное переполнение в случае большого S, вероятно надо использовать большие числа.
Исправление
Legioner,
:
Без оптимизации так:
считаем сумму всех элементов. S = sum_x_y xy[j]
выбираем число от 0 до S - 1. t := random [0, S)
Дальше псевдокод:
[br]for i <- 0 .. 1000[br] for j <- 0 .. 1000[br] t := t - xy[i][j];[br] if t < 0[br] return (i, j)[br]Чтобы оптимизировать, надо хранить суммы по строкам. Дальше - сначала находим строку, потом в ней находим столбец.
Возможно целочисленное переполнение в случае большого S, вероятно надо использовать большие числа.
Исходная версия
Legioner,
:
Без оптимизации так:
считаем сумму всех элементов. S = sum_x_y xy[j]
выбираем число от 0 до S - 1. t := random [0, S)
Дальше псевдокод:
[code]
for i <- 0 .. 1000
for j <- 0 .. 1000
t := t - xy[j];
if t < 0
return (i, j)
[/code]
Чтобы оптимизировать, надо хранить суммы по строкам. Дальше - сначала находим строку, потом в ней находим столбец.
Возможно целочисленное переполнение в случае большого S, вероятно надо использовать большие числа.