В файле записаны неповторяющиеся числа.
Необходимо за один проход и без использования массивов определить, можно ли их записать в виде арифметической прогрессии.
Например
2 10 8 6 4
можно представить в виде 2 4 6 8 10 — арифметическая прогрессия d=2
Здравствуйте, Аноним, Вы писали:
А>В файле записаны неповторяющиеся числа. А>Необходимо за один проход и без использования массивов определить, можно ли их записать в виде арифметической прогрессии. А>Например
А>2 10 8 6 4 А>можно представить в виде А>2 4 6 8 10 — арифметическая прогрессия d=2
А>Числа А>1 3 5 9 11, нельзя — пропущена 7
Проходишь по файлу и одновременно делаешь слудующее:
1. Запоминаешь наименьшее число Min
if (Value < Min) Min = Value;
2. Запоминаешь наибольшее число Max
if (Value > Max) Max = Value;
3. Запоминаешь наименьшую по модулю разность между двумя соседними числами Diff
if (CurDiff < Diff) Diff = CurDiff;
4. Запоминаешь количество чисел в файле. Cnt
Cnt++
Потом
return ( ( ( Max - Min ) / Cnt ) == Diff ) ? true : false;
Здравствуйте, UgN, Вы писали:
UgN>1. Запоминаешь наименьшее число Min UgN>2. Запоминаешь наибольшее число Max UgN>3. Запоминаешь наименьшую по модулю разность между двумя соседними числами Diff UgN>4. Запоминаешь количество чисел в файле. Cnt UgN>Потом UgN>
UgN>return ( ( ( Max - Min ) / Cnt ) == Diff ) ? true : false;
UgN>
Здравствуйте, Аноним, Вы писали:
А>В файле записаны неповторяющиеся числа. А>Необходимо за один проход и без использования массивов определить, можно ли их записать в виде арифметической прогрессии.
За один проход ищем минимальное и максимальное число и сумму всех чисел(ну и заодно запоминаем количество чисел, если не было известно заранее)
берем формулу для суммы элементов прогресси, считаем, и сверяем с полученной ранее суммой.
Здравствуйте, Bell, Вы писали:
B>За один проход ищем минимальное и максимальное число и сумму всех чисел(ну и заодно запоминаем количество чисел, если не было известно заранее) B>берем формулу для суммы элементов прогресси, считаем, и сверяем с полученной ранее суммой.
3.1 Запоминаешь наименьшую по модулю разность между первым и последующими числами DiffA
3.2 Запоминаешь наименьшую по модулю разность между соседними числами DiffB
Здравствуйте, Аноним, Вы писали:
А>В файле записаны неповторяющиеся числа. А>Необходимо за один проход и без использования массивов определить, можно ли их записать в виде арифметической прогрессии.
Вариант А.
1. Находим минимальное a_1
2. Находим второе по величине a_2. d=a_2-a_1.
3. Находим максимальное a_n
4. Находим НОД всех разниц пар чисел, которые идут подряд в последовательности.
5. Считаем n
Утверждение. Если НОД делится на d и a_n=a_1+(n-1)*d, то а.п., иначе — не а.п.
Обоснование. То что НОД делится на d обозначает что модуль разницы любой пары чисел последовательности не больше d.
Вариант Б.
1. Находим минимальное a_1
2. Находим второе по величине a_2. d=a_2-a_1.
3. Находим сумму всех чисел S
4. Находим произведение всех чисел P
5. Считаем n
Сумма S и произведение P должны совпадать с суммой а.п. с первым членом a_1 и разницей d.
Пока обосновать строго не получилось. Но интуитивно — вроде так.
Здравствуйте, Atilla, Вы писали:
A>Здравствуйте, seug, Вы писали:
A> S>>В этом месте надо считать не минимальную разность 2 соседних чесел, а НОД разностей
A>о! вот теперь правильно. A>Только можно не сумму считать, а минимум и максимум.
Какже ты предлагаешь обойтись без суммы?
А минимум и максимум и так считаются.
Здравствуйте, Аноним, Вы писали:
А>В файле записаны неповторяющиеся числа. А>Необходимо за один проход и без использования массивов определить, можно ли их записать в виде арифметической прогрессии.
Пусть мы даже не знаем изначально количество чисел (текстовый файл).
Что мы можем измерить за один проход...
Для прогрессии с шагом D, разность d[i,j] двух любых членов a[i], a[j] равна (j-i)*D.
Следовательно, НОД(d1,d2) = k*S. НОД(всех d) = D.
Достаточно приложиться к разностям соседних чисел файла.
D = |f[1]-f[0]|
for i = 2 .. end_of_file
D = НОД(D, |f[i]-f[i-1]|)
Далее, если мы насчитали N чисел, то для прогрессии выполняется |a_max-a_min| == (N-1)*D.
(минимальное и максимальное числа находятся элементарно)
Критерий недостаточный: контрпример: 1 2 3 5 3 6 7 8
Однако для неповторяющихся чисел, возможно, он достаточен (надо подумать...)
Еще один критерий.
Сумма прогрессии S = a[0]+...+a[N-1] = a_min + N*(N-1)/2*D.
(сумма чисел считается за этот же проход)
Критерий также недостаточный: 1 2 7 2 7 2 7 8
Та же самая ремарка.
Здравствуйте, seug, Вы писали:
S>Какже ты предлагаешь обойтись без суммы?
Ну как, есть массив
a0, a1, ... an
считаем в 1 проход max(a), min(a), и D=НОД(a[i+1]-a[1])
получается, что a[i+1]-a[i]=D*k[i+1] или
a[i]=a[0]+(k[1]+...k[i])*D
пусть шаг прогрессии равен C*D, C>1, тогда любая разность будет делиться на C*D и НОД!=D.
или так: a[i]=Min+D*K[i], т.е. шаг прогрессии (если она имеет место быть) d может быть только делителем.
Альтернатива — прогрессии нет, а есть подпоследовательность прогрессии с шагом d, которая — делитель D. Вот...
Пусть D=C*d, C>1
возьмем полную последовательность от min до max с шагом d.
а {a} — это на самом деле подпоследовательность, которая не является арифметической с шагом D.
Т.е. существует по крайнем мере один элемент a[x]=min+d*X, причем d*X не делится на D. Тогда, т.к. разница с соседями делится на D, то соседние тоже такие: a[x-1]=min+d*X1, a[x+1]=min+d*X2, где d*X1 и d*X2 не делятся на D.
Ну и аналогично, получается, что каждый элемент a[i]=min+d*Xi, причем d*Xi не делится на D для всех i, даже для минимума. Ну а такое — невозможно.
Остается последний вариант: {a} — подпоследовательность ар. прогрессии с шагом D. Проверить это — элементарно:
если (min-max)/(n-1)=D, то прогрессия, иначе — подпоследовательность
вроде нигде не наврал
S>А минимум и максимум и так считаются.
Пусть мы нашли НОД всех смежных разностей (а также всех разностей с первым, с локально минимальным, с локально максимальным элементами — сколько угодно).
Тогда, без потери общности задачи, мы можем взять эквивалентный файл, такой, что его минимальный элемент = 0 (т.е. вычли f_min из всех элементов f), а НОД равен 1 (поделили (f-f_min) на НОД).
То есть свели задачу к такой: можно ли для набора разных неотрицательных чисел определить — является ли он арифметической прогрессией вида 0,1,2,...k...
Ответ: конечно, да!
Предположим, что у нас N чисел (и все они разные по условиям задачи; мы это утверждение дополнительно не проверяем!).
Тогда они будут являться указанной прогрессией тогда и только тогда, когда минимум = 0, а максимум = N-1.
Доказательство очевидно: пусть в наборе есть "щербина" (отсутствуют некоторые числа прогрессии). Тогда, если минимум = 0 и максимум = M-1, то количество N будет меньше, чем M.
А если щербины нет, то M==N.
Повторяться числа не могут по условию, поэтому вариант N>M, а также компенсация щербин повторами невозможна.
Теперь вернем все на место: каждый элемент натуральной прогрессии умножим на D и прибавим f_min.
Таким образом, алгоритм проверки найден:
1) находим D = НОД((f[0]-f[k]) для всех k), f_min, f_max, N
2) проверяем f_min + D*(N-1) == f_max.
В нашем доказательстве мы исходили из того, что D>0 (делили и умножали на него). Очевидно, что случай D==0 говорит о том, что одна из разностей оказалась нулевой, то есть в файле встретился повтор.
Большую часть работы ты проводишь, чтобы сказать: все числа (относительно первого) кратны шагу прогрессии, который был найден как НОД всех разностей. Это как бы масло масляное: все разности кратны НОД от их всех
Меня же как раз волновало доказательство того, что (N-1)*D=(max-min) есть необходимое и достаточное условие (которое ты упомянул всколзь).
Здравствуйте, Кодт, Вы писали:
К>Большую часть работы ты проводишь, чтобы сказать: все числа (относительно первого) кратны шагу прогрессии, который был найден как НОД всех разностей. Это как бы масло масляное: все разности кратны НОД от их всех
Просто я долго не мог понять, это очевидно или не очень
Как говорил мой школьный учитель (покайный ) "очевидное — это то, что легко доказать". Вот я и решил доказать.
К>Меня же как раз волновало доказательство того, что (N-1)*D=(max-min) есть необходимое и достаточное условие (которое ты упомянул всколзь).
Ну а это, по-моему и ежу понятно. Если шаг прогрессии может быть только D и никак иначе, то проверка сразу получается.
В общем, разница была только в том, кто что считал очевидным
Кр-ть — с.т.
Перекуём баги на фичи!
) "очевидное — это то, что легко доказать". Вот я и решил доказать. 
