Нужна подсказка

@kkk008009kkk · Регистрация: 24.03.2011

Студворк — интернет-сервис помощи студентам

Добрый день.

Имеются 2 задачи(см. вложения).

Никак не могу решить. Задачи(задали с десяток) заданы с целью научить думать. Но не думается.

Дайте, пожалуйста, какую-нибудь подсказку/зацепку с какого направления "копать".

@Севак · 07.04.2012, 19:29

kkk008009kkk, я думаю так: находишь сумму, потом переменной какой-нибудь задаешь разницу q и модуля суммы, наименьшее значение и будет ответом ( а точнее нам же нужен номер, так что при присваивании надо еще запомнить номер)

Добавлено через 2 минуты
второй (что-то наподобие делал) задаем 2 цикла for i:=1 to n for k:=1 to n и смотрим, равна ли сумма элемента s и ставим условие чтобы i<>k

@kkk008009kkk · 07.04.2012, 19:35 **[ТС]**

Севак,Во второй задаче сумма может быть представлена и тремя элементами массива.

А в первой какую сумму найти? Вида x[i]+y[j]? Так её я и не могу найти.

@Севак · 07.04.2012, 19:42

kkk008009kkk, а нельзя создать еще один массив q[i]:=x[i]+y[i]?
насчет второй, чтобы уменьшить диапазон искомых чисел (если все числа положительные) в отдельный массив запишем числа меньшие заданного (т.к. больше нам уже не подходят, если, конечно, нет отрицательных чисел в массиве), пока подумаю как организовать чтобы сумму нескольких чисел считал

@Somebody · 07.04.2012, 22:10

Сообщение от Севак

а нельзя создать еще один массив q[i]:=x[i]+y[i]?

x[i] + y[i] - зачем?
x[i] + y[j] - это уже больше действий, чем k + l.

@#pragma · 10.05.2012, 19:59

Интересные задачи.

Насчёт задачи с двумя массивами. Есть такая идея (жаль только я матчасть пока не выучил, так что идея может быть неудачной):

1. Берём средний элемент из массива x (x[i]) в первом цикле.
2. Затем средний элемент из массива y (y[j]) во втором цикле (вложенном).
3. Складываем и сравниваем с q.
4. Если сумма больше q, то следующий элемент y[j] берём из меньшей половины массива y, снова поделив его пополам. Снова сравниваем сумму.
5. Продолжаем до тех пор, пока двигаться будет некуда. То есть движение всегда идёт скачками по половине текущего диапазона.
6. Запоминаем самый последний результат. (Пока что он самый лучший в этом проходе). Тут надо ещё подумать, возможно необходимо запоминать два последних.
7. В зависимости от того, больше он, или меньше q, берём следующий элемент массива x, снова поделив его пополам. Продолжаем те же действия (2-7) , что и раньше.

@kkk008009kkk · 11.05.2012, 15:00 **[ТС]**

#pragma, Спасибо, попробую. Так и не решил пока. Задач задали много, на разные темы, поэтому совет актуален.

@Christopher M. · 16.05.2012, 21:12

Сообщение от #pragma

1. Берём средний элемент из массива x (x[i]) в первом цикле.
2. Затем средний элемент из массива y (y[j]) во втором цикле (вложенном).
3. Складываем и сравниваем с q.
4. Если сумма больше q, то следующий элемент y[j] берём из меньшей половины массива y, снова поделив его пополам. Снова сравниваем сумму.
5. Продолжаем до тех пор, пока двигаться будет некуда. То есть движение всегда идёт скачками по половине текущего диапазона.
6. Запоминаем самый последний результат. (Пока что он самый лучший в этом проходе). Тут надо ещё подумать, возможно необходимо запоминать два последних.
7. В зависимости от того, больше он, или меньше q, берём следующий элемент массива x, снова поделив его пополам. Продолжаем те же действия (2-7) , что и раньше.

Интересный подход. Косяк, на самом деле, только один - в условии выхода. В "Продолжаем до тех пор, пока двигаться будет некуда". Трудно его сформулировать при таких прыжках. А если учесть, что числа в массивах могут возрастать неравномерно, то мы вообще рискуем "пролететь" решение, и не понять когда это произошло.

Я предложил бы не заморачиваться:

Code
1
2
3
4
5
6
7
8
9
10
начиная с i = 1 и j = 1
_нц:
считаем сумму x[i] + y[j]
если сумма больше q:
  запоминаем значения i и j в переменные a и b
  запоминаем сумму в с
  берем следующий i = i +1, если x[i + 1] меньше y[j + 1] [B]или[/B] следующий j = j + 1, если x[i + 1] больше y[j + 1]
  переходим к _нц. 
как только сумма стала больше q:
  сравниваем переменную с и новую сумму с q, то, что отличается на меньшее значение - то и берем в результат.

То есть, если по русски, двигаться прямо сверху с минимальным шагом изменения суммы. Переменными в условия попадаем. Единственный косяк, непонятно, что считать за одну операцию. Так как сложность выполнения тела цикла не зависит от размера массивов (только число выполнений тела цикла зависит от k и l), его можно принять как константу и не особо брать в рассчет при оценке сложности. То есть, если бы задача была не учебная, в этом плане явно все кошерно.
Если же посчитать количество операций в теле цикла, включая все сравнения, сложения и присваивания - то 7 (кажется?) операций в теле цикла на в худшем случае k + l его выполнений да некоторые туда сюда в начале и конце - это больше чем k + l факт.

P.S. и - да - я не учел в алгоритме случаи когда первая или последняя сумма окажется искомой. Просили таки подсказку а не готовое решение...

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315

	Нужна подсказка 07.04.2012, 12:04. Показов 1117. Ответов 7 Метки нет (Все метки) Добрый день. Имеются 2 задачи(см. вложения). Никак не могу решить. Задачи(задали с десяток) заданы с целью научить думать. Но не думается. Дайте, пожалуйста, какую-нибудь подсказку/зацепку с какого направления "копать". Миниатюры 0

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	07.04.2012, 19:29
	kkk008009kkk, я думаю так: находишь сумму, потом переменной какой-нибудь задаешь разницу q и модуля суммы, наименьшее значение и будет ответом ( а точнее нам же нужен номер, так что при присваивании надо еще запомнить номер) Добавлено через 2 минуты второй (что-то наподобие делал) задаем 2 цикла for i:=1 to n for k:=1 to n и смотрим, равна ли сумма элемента s и ставим условие чтобы i<>k 1

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315
	07.04.2012, 19:35 [ТС]
	Севак,Во второй задаче сумма может быть представлена и тремя элементами массива. А в первой какую сумму найти? Вида x[i]+y[j]? Так её я и не могу найти. 0

@Севак любитель покушать 687 / 641 / 248 Регистрация: 25.09.2011 Сообщений: 1,313
	07.04.2012, 19:42
	kkk008009kkk, а нельзя создать еще один массив q[i]:=x[i]+y[i]? насчет второй, чтобы уменьшить диапазон искомых чисел (если все числа положительные) в отдельный массив запишем числа меньшие заданного (т.к. больше нам уже не подходят, если, конечно, нет отрицательных чисел в массиве), пока подумаю как организовать чтобы сумму нескольких чисел считал 1

@#pragma Временно недоступен 957 / 228 / 14 Регистрация: 12.04.2009 Сообщений: 926
	10.05.2012, 19:59
	Интересные задачи. Насчёт задачи с двумя массивами. Есть такая идея (жаль только я матчасть пока не выучил, так что идея может быть неудачной): 1. Берём средний элемент из массива x (x[i]) в первом цикле. 2. Затем средний элемент из массива y (y[j]) во втором цикле (вложенном). 3. Складываем и сравниваем с q. 4. Если сумма больше q, то следующий элемент y[j] берём из меньшей половины массива y, снова поделив его пополам. Снова сравниваем сумму. 5. Продолжаем до тех пор, пока двигаться будет некуда. То есть движение всегда идёт скачками по половине текущего диапазона. 6. Запоминаем самый последний результат. (Пока что он самый лучший в этом проходе). Тут надо ещё подумать, возможно необходимо запоминать два последних. 7. В зависимости от того, больше он, или меньше q, берём следующий элемент массива x, снова поделив его пополам. Продолжаем те же действия (2-7) , что и раньше. 1

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315
	11.05.2012, 15:00 [ТС]
	#pragma, Спасибо, попробую. Так и не решил пока. Задач задали много, на разные темы, поэтому совет актуален. 0