Помоготе решить задачу

@kapka · Регистрация: 04.01.2011

Составить программу, которая выводит минимальное количество гирь, необходимых для взвешивания любого тела, масса которого не превышает М. Масса тела - целое число. Гирьки можно ставить на обе части весов.
Например, для М=100 ответ 5. Для М=9 - 3.

@Barbarosa · 18.01.2011, 17:24

Было бы неплохо уловия поподробней.

@palva · 18.01.2011, 17:36

Код

Для произвольного M > 0 определить минимальное n, такое что
   существуют i1, i2, ..., in > 0 (гирьки) такие что
      любое неотрицательное m >= M представимо в виде
      m = d1*i1 + d2*i2 + ... + dn*in, где d1, ..., dn
      принимает одно из трех значений: -1, 0, 1.

@palva · 18.01.2011, 17:39

любое неотрицательное m <= M представимо в виде...

@Vit54 · 18.01.2011, 21:08

Пусть m1 - вес сaмoй тяжелoй гири. Делишь М нa m1, чaстнoе oт деления - кoличествo гирь весoм m1. Oстaтoк делишь нa m2 - вес сaмoй тяжёлoй из oстaвшихся гирь, чaстнoе oт деления - кoличествo гирь весoм m2. И т. д. Вoт тaкaя cхемa. Пo-мoему, легкo уклaдывaется в цикл. Ну и пoсле кaждoгo деления прoверяешь не рaвен ли oстaтoк нулю.

@palva · 19.01.2011, 00:11

Что-то я совсем плохой стал. Сам же формализовал задачу, а не увидел в записи троичной системы счисления. Короче, решение такое: Гири выбираем подряд из последовательности 1, 3, 9, 27 ... (степени тройки)пока сумма гирь не достигнет числа M. Соответственно и программа может вычислять сумму степеней тройки, либо можно выразить искомое число гирь через троичный логарифм. Ну а все доказательства можно поискать у Кнута в первом томе. Либо вспомнить представление чисел в троичной ЭВМ 'Сетунь' (1960-е годы). Там в качестве цифр троичного представления использовались -1, 0, +1. Например число -5 представлялось как (-1)(+1)(+1)

@kapka · 21.01.2011, 12:06 **[ТС]**

Большое спасибо! Не мог этого увидеть...

@kapka · 21.01.2011, 12:19 **[ТС]**

Я вижу, что есть любители поупражняться. А у меня есть еще нерешенные задачи. Предлагаю:
Подсчитать количество n-разрядных чисел, которые местят две семерки, что стоят рядом. Тупой перебор не проходит - нужно уложиться в две секунды.
Например, для n=3 чисел будет 18:
177,277,377,477,577,677,770,77 1,772,773,774,775,776,777,778, 779,877,977.

@Barbarosa · 23.01.2011, 12:29

Если n - количество цифр в числе, то в одном положении 2-х семерок имеем:
(10^(n-2)) - 1 чисел,
количество различных положений двух рядом стоящих семерок в числе: n-1.
Соответственно получаем:
((10^(n-2))-1)*(n-1), n>2

@kapka · 23.01.2011, 14:44 **[ТС]**

Еще такую не могу решить:
258252278254260246230236230192 250254192270230
Здесь закодировано сообщение. Только большие латинские буквы и некоторые стандартные знаки препинания. Нужно прочесть.

@Barbarosa · 23.01.2011, 18:50

Это уже ИМХО из области криптографии.

@kapka 0 / 0 / 0 Регистрация: 04.01.2011 Сообщений: 4
		1
	Помоготе решить задачу 04.01.2011, 20:21. Показов 1345. Ответов 10 Метки нет (Все метки) Составить программу, которая выводит минимальное количество гирь, необходимых для взвешивания любого тела, масса которого не превышает М. Масса тела - целое число. Гирьки можно ставить на обе части весов. Например, для М=100 ответ 5. Для М=9 - 3. __________________ Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь 0

@Barbarosa 4 / 4 / 0 Регистрация: 11.06.2008 Сообщений: 27
	18.01.2011, 17:24	2
	Было бы неплохо уловия поподробней. 0

@palva 3882 / 2807 / 651 Регистрация: 08.06.2007 Сообщений: 9,559 Записей в блоге: 4
	18.01.2011, 17:39	4
	любое неотрицательное m <= M представимо в виде... 0

@Vit54 0 / 0 / 0 Регистрация: 21.05.2007 Сообщений: 252
	18.01.2011, 21:08	5
	Пусть m1 - вес сaмoй тяжелoй гири. Делишь М нa m1, чaстнoе oт деления - кoличествo гирь весoм m1. Oстaтoк делишь нa m2 - вес сaмoй тяжёлoй из oстaвшихся гирь, чaстнoе oт деления - кoличествo гирь весoм m2. И т. д. Вoт тaкaя cхемa. Пo-мoему, легкo уклaдывaется в цикл. Ну и пoсле кaждoгo деления прoверяешь не рaвен ли oстaтoк нулю. 0

@palva 3882 / 2807 / 651 Регистрация: 08.06.2007 Сообщений: 9,559 Записей в блоге: 4
	19.01.2011, 00:11	6
	Что-то я совсем плохой стал. Сам же формализовал задачу, а не увидел в записи троичной системы счисления. Короче, решение такое: Гири выбираем подряд из последовательности 1, 3, 9, 27 ... (степени тройки)пока сумма гирь не достигнет числа M. Соответственно и программа может вычислять сумму степеней тройки, либо можно выразить искомое число гирь через троичный логарифм. Ну а все доказательства можно поискать у Кнута в первом томе. Либо вспомнить представление чисел в троичной ЭВМ 'Сетунь' (1960-е годы). Там в качестве цифр троичного представления использовались -1, 0, +1. Например число -5 представлялось как (-1)(+1)(+1) 0

@kapka 0 / 0 / 0 Регистрация: 04.01.2011 Сообщений: 4
	21.01.2011, 12:06 [ТС]	7
	Большое спасибо! Не мог этого увидеть... 0

@kapka 0 / 0 / 0 Регистрация: 04.01.2011 Сообщений: 4
	21.01.2011, 12:19 [ТС]	8
	Я вижу, что есть любители поупражняться. А у меня есть еще нерешенные задачи. Предлагаю: Подсчитать количество n-разрядных чисел, которые местят две семерки, что стоят рядом. Тупой перебор не проходит - нужно уложиться в две секунды. Например, для n=3 чисел будет 18: 177,277,377,477,577,677,770,77 1,772,773,774,775,776,777,778, 779,877,977. 0

@Barbarosa 4 / 4 / 0 Регистрация: 11.06.2008 Сообщений: 27
	23.01.2011, 12:29	9
	Если n - количество цифр в числе, то в одном положении 2-х семерок имеем: (10^(n-2)) - 1 чисел, количество различных положений двух рядом стоящих семерок в числе: n-1. Соответственно получаем: ((10^(n-2))-1)*(n-1), n>2 0

@kapka 0 / 0 / 0 Регистрация: 04.01.2011 Сообщений: 4
	23.01.2011, 14:44 [ТС]	10
	Еще такую не могу решить: 258252278254260246230236230192 250254192270230 Здесь закодировано сообщение. Только большие латинские буквы и некоторые стандартные знаки препинания. Нужно прочесть. 0

@Barbarosa 4 / 4 / 0 Регистрация: 11.06.2008 Сообщений: 27
	23.01.2011, 18:50	11
	Это уже ИМХО из области криптографии. 0

Опции темы