Предыдущая тема :: Следующая тема
|
Автор |
Сообщение |
Sir Kot

Зарегистрирован: 21.10.2003 Сообщения: 892 Откуда: Korolev City Computer Network
|
Добавлено: 07 Ноя 2006, 00:59 Заголовок сообщения: |
|
|
Nouzui писал(а): | а у меня невскидку 19!
причем я не верил, что можно обойтись за 14
прочитал решение, поверил... |
Эмм... а деление отрезка попалам.... раз за 7-8 можно уложиться...
О! Пока я тут на два делил, PGM меня обогнал  _________________ Вы спрашиваете, мы отвечаем. Неофициальная энциклопедия сети Королев.Нет |
|
Вернуться к началу |
|
|
Nouzui
Зарегистрирован: 07.06.2005 Сообщения: 310
|
Добавлено: 07 Ноя 2006, 01:03 Заголовок сообщения: |
|
|
Цитата: | Есть два стеклянных шарика |
рисковать нельзя.. ) |
|
Вернуться к началу |
|
|
PGM
Зарегистрирован: 24.10.2003 Сообщения: 68 Откуда: Королев
|
Добавлено: 07 Ноя 2006, 01:26 Заголовок сообщения: |
|
|
Nouzui писал(а): | Цитата: | Есть два стеклянных шарика |
рисковать нельзя.. ) |
Извиняюсь - не заметил - две попытки серьезно осложняют жизнь. Однако решение красивое - действительно 14. А как на счет трех шариков и 100 этажей?
P.S. Единственная проблема - шарики от тестов могут деградировать и данные эксперимента будут неверны . _________________ "Не ботфортом консомэ хлебаем" |
|
Вернуться к началу |
|
|
Nouzui
Зарегистрирован: 07.06.2005 Сообщения: 310
|
Добавлено: 07 Ноя 2006, 01:31 Заголовок сообщения: |
|
|
PGM писал(а): |
Однако решение красивое - действительно 14. А как на счет трех шариков и 100 этажей? |
ммм.. думать уже влом
я тут, собственно, программулину соорудил. для сотни реально пишет - 14. мож ее и для трех шариков можно переделать...
а вообще общая постановка - N шариков, M этажей
для случая N<M я сразу сдаюсь )
PGM писал(а): |
P.S. Единственная проблема - шарики от тестов могут деградировать и данные эксперимента будут неверны . | )) |
|
Вернуться к началу |
|
|
Mars

Зарегистрирован: 26.02.2006 Сообщения: 56
|
Добавлено: 07 Ноя 2006, 07:12 Заголовок сообщения: |
|
|
Whisper писал(а): | Да уж, философ с математическим образованием
Какая там линейность? Как диаметр разлёта оценивать? Все законы физики линейны? Оооооо... Даже если взять элементарное падение шарика с высоты - зависимость квадратичная! Для аппроксимации параболы минимум нужны три точки, а у тебя всего три попытки! А скорректировать можно только дорогу, на которую эти шарики упадут
Думаю, здесь всё-таки про метод проб и ошибок У меня получилось 15 |
Все законы физики линейны, не забывайте что любую функцию мы можем разложить в ряд Тейлора, откинув порядок старше первого. А дальше необходимо подобрать весовые коэфициенты, накройняк привести фильтрацию, я бы предложил Калмана. А так, утверждаю со всей ответственностью трех попыток как за нефик. Если будет время и настроение распишу теорию. Правда я сомневаюсь что тут много тех, кто хотя бы азы теоретической физики изучил)))
не обижайтесь)))) |
|
Вернуться к началу |
|
|
Mars

Зарегистрирован: 26.02.2006 Сообщения: 56
|
Добавлено: 07 Ноя 2006, 07:14 Заголовок сообщения: |
|
|
а поповоду оценки падения, то нам не нужно ничего кроме конечной скорости, а она как бы не является квадратичной))) |
|
Вернуться к началу |
|
|
Nouzui
Зарегистрирован: 07.06.2005 Сообщения: 310
|
Добавлено: 07 Ноя 2006, 13:59 Заголовок сообщения: |
|
|
PGM писал(а): | А как на счет трех шариков и 100 этажей?
|
9
вот код:
Код: | #define MaxFloorsCount 100
#define MaxSpheriesCount 2
int Find(int nFloorsCount, int nSpheriesCount);
int Check(int nFloorsCount, int nSpheriesCount);
#define COUNT_INDEX 0
#define FIRSTFLOOR_INDEX 1
#define FLAG_INDEX 2
int nCheckCache[MaxFloorsCount+1][MaxSpheriesCount][3];
int main()
{
// TODO: Place code here.
int i;
printf("Result: %d\n", Find(MaxFloorsCount, MaxSpheriesCount));
printf("Sequence:\n");
for(i= 0; i<MaxFloorsCount;)
{
i+= nCheckCache[MaxFloorsCount-i][MaxSpheriesCount-1][FIRSTFLOOR_INDEX];
printf("Floor number %d\n", i);
}
return 0;
}
int Find(int nFloorsCount, int nSpheriesCount)
{
int i, j;
if(nFloorsCount<0 || nFloorsCount>MaxFloorsCount || nSpheriesCount<1 || nSpheriesCount>MaxSpheriesCount)
{
printf("Error\n");
exit(0);
}
for(i= 0; i<=MaxFloorsCount; i++)
for(j= 0; j<MaxSpheriesCount; j++)
nCheckCache[i][j][FLAG_INDEX]= 0;
return Check(nFloorsCount, nSpheriesCount);
}
int Check(int nFloorsCount, int nSpheriesCount)
{
int i;
int nResult;
int nFirstFloor;
int nTempResult;
if(!nSpheriesCount)
{
printf("Error: nSpheriesCount==0\n");
exit(0);
}
if(nCheckCache[nFloorsCount][nSpheriesCount-1][FLAG_INDEX])
return nCheckCache[nFloorsCount][nSpheriesCount-1][COUNT_INDEX];
if(nFloorsCount==0)
{
nResult= 0;
nFirstFloor= 0;
}
else if(nSpheriesCount==1)
{
nResult= nFloorsCount;
nFirstFloor= 1;
}
else if(nFloorsCount==1)
{
nResult= 1;
nFirstFloor= 1;
}
else
{
nFirstFloor= 1;
nResult= Check(nFloorsCount-1, nSpheriesCount);
for(i= 2; i<=nFloorsCount; i++)
{
nTempResult= max(Check(i-1, nSpheriesCount-1), Check(nFloorsCount-i, nSpheriesCount));
if(nTempResult<=nResult)
{
nResult= nTempResult;
nFirstFloor= i;
}
}
nResult++;
}
nCheckCache[nFloorsCount][nSpheriesCount-1][COUNT_INDEX]= nResult;
nCheckCache[nFloorsCount][nSpheriesCount-1][FIRSTFLOOR_INDEX]= nFirstFloor;
nCheckCache[nFloorsCount][nSpheriesCount-1][FLAG_INDEX]= 1;
return nResult;
} |
последовательность в этом случае (пока целы все три шара) будет такой:
Floor number 37
Floor number 59
Floor number 75
Floor number 86
Floor number 93
Floor number 97
Floor number 99
Floor number 100
когда первый шар разбивается, оставшийся промежуток проходится уже с двумя шарами
уфф.. )
сначала программулина была на прологе, но когда выяснилось, что уже для 15 этажей она заметно подтормаживает, я решил переписать ее на C - в нем, по крайней мере, можно запомнить результат функции и не вычислять ее повторно... на прологе такое, вроде, не сделаешь |
|
Вернуться к началу |
|
|
thresh

Зарегистрирован: 21.10.2003 Сообщения: 633
|
Добавлено: 07 Ноя 2006, 14:36 Заголовок сообщения: |
|
|
не собирается
/tmp/.private/thresh/cchDmm0z.o: In function `Check':
file.c:(.text+0x24a): undefined reference to `max' |
|
Вернуться к началу |
|
|
Кн. Тошнотворец

Зарегистрирован: 05.01.2005 Сообщения: 367 Откуда: Queens-City
|
Добавлено: 07 Ноя 2006, 14:52 Заголовок сообщения: |
|
|
thresh писал(а): | не собирается
/tmp/.private/thresh/cchDmm0z.o: In function `Check':
file.c .text+0x24a): undefined reference to `max' |
попробуй "#include <math.h>" _________________ -Я эльф!
-Все мы немножечко эльфы...
-Я Феанор!
-Без этого сегодня никуда...
-Что же мне делать?
-Для начала повернись задом и приспусти штаны, я сделаю тебе укольчик... (с) Eldaron |
|
Вернуться к началу |
|
|
thresh

Зарегистрирован: 21.10.2003 Сообщения: 633
|
Добавлено: 07 Ноя 2006, 15:13 Заголовок сообщения: |
|
|
нет, функции max там нет |
|
Вернуться к началу |
|
|
thresh

Зарегистрирован: 21.10.2003 Сообщения: 633
|
Добавлено: 07 Ноя 2006, 15:15 Заголовок сообщения: |
|
|
помогло впрочем include <sys/param.h> и замена max на MAX |
|
Вернуться к началу |
|
|
Mars

Зарегистрирован: 26.02.2006 Сообщения: 56
|
Добавлено: 15 Ноя 2006, 05:41 Заголовок сообщения: |
|
|
Whisper писал(а): | Да уж, философ с математическим образованием
|
Я МФТИ закончил))) Сейчас просто в аспирантуре при РКК учусь, пришлось работу по философии писать. |
|
Вернуться к началу |
|
|
Nouzui
Зарегистрирован: 07.06.2005 Сообщения: 310
|
Добавлено: 05 Фев 2007, 12:52 Заголовок сообщения: |
|
|
что-нибудь можно сделать? |
|
Вернуться к началу |
|
|
Графиня*

Зарегистрирован: 15.09.2004 Сообщения: 124
|
Добавлено: 05 Фев 2007, 21:10 Заголовок сообщения: |
|
|
Nouzui писал(а): | [img................
что-нибудь можно сделать? |
ткнуть пальцем в небо оч. даже можно _________________ Не учите меня жить, и я не скажу вам куда идти |
|
Вернуться к началу |
|
|
Whisper

Зарегистрирован: 15.06.2006 Сообщения: 102 Откуда: Ночной кошмар
|
Добавлено: 06 Фев 2007, 02:08 Заголовок сообщения: |
|
|
Не учли создатели некоторых спорных ситуаций, у меня постоянно такие выпадают!
Ноузуи, придумай своего сапера, который не глючит, и продвинь!  _________________ [url=http://slingokonsultant.ru/ticker/][/url] |
|
Вернуться к началу |
|
|
|