Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2 3 4 ... 7   Вниз
  Печать  
Автор Тема: Задачка - мозги поразмять ;)  (Прочитано 76631 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mouse
Молодой специалист

ru
Offline Offline

« : 30-06-2004 19:15 » 

Задача:
Имеется фирма, доход которой определяется по формуле: 2 в степени доход за предыдущий месяц. Т.е. доход в первый месяц составит 2$, во второй - 2^2 = 4$, в третий - 2^4 = 16$, в четвертый - 2^16 = 65536$, в пятый - 2^65536 = ...
Далее: фирмой управляет N человек. Они решили делить ежемесячный доход поровну, а остаток отдавать на благотворительность. Например: при N = 5 в третьем месяце на благотворительность уйдет (16 % 5) = 1$.
Задача проста - найти, сколько денег будет потрачено на благотворительность в M-м месяце, если фирму возглавляет N человек. Фактически надо найти остаток от деления дохода в любом месяце на произвольное число.

Кто решит - тот джигит!
Записан
PSD
Главный специалист

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 22-07-2004 10:52 » 

А каоке решение нужно? такое подайдет ?

m='номер месяца
n='Число людей


d=2
for i= 1 to m
d=2^d
next i

Xolava= (d-(d\N)*N)
Записан

Да да нет нет все остальное от лукавого.
Mouse
Молодой специалист

ru
Offline Offline

« Ответ #2 : 23-07-2004 12:42 » 

PSD, для маленьких d - подойдет. Вот только на 6-м месяце ты получишь доход d = 2^65536!  Я шокирован! Вопрос здесь как раз в том, как избежать переполнения...  :?:
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 23-07-2004 15:57 » 

Archangel,
Код:
#define Nd 3
DWORD d[Nd];
int i;

d[0]=2;
for(i=1;i<m;i++) d[i]=1;

int k=0;
for(i=0;i<m;i++)
{
d[k++] *= 2;
k=(k==Nd ? 0 : k);
}

//так получили число d в виде d[0]*d[1]*d[2]*...*d[Nd-1]

теперь как-то надо остаток определить
« Последнее редактирование: 29-11-2007 15:52 от Алексей1153++ » Записан

Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 23-07-2004 16:29 » 

Цитата

теперь как-то надо остаток определить


может так:

пусть для примера Nd=2, тогда:

#define D(n) ((double)n)

double Npart=D(N)/Nd

//d==d0*d1;

//(d[0]*d[1]) / N == ( (D(d[0])/( Npart )) * (D(d[1])/( Npart )) ) == d0*d1

теперь если представить все числа d0,d1 ...  (они типа double) в виде:
(d0_a + d0_d), (d1_a + d1_d), где с постфиксом _a - целая часть, _d - дробная.

если скобки раскрыть и оставить сумму только тех членов, где оба множителя - не целые, а затем дробную часть полученной суммы умножить на N - это вроде и должен быть искомый остаток
(но может где-то я и неправ - не спорю Улыбаюсь )
Записан

Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 23-07-2004 16:51 » 

блин, облейте меня водой (t=-10)!!! , всё ещё проще Улыбаюсь

Цитата

m='номер месяца
n='Число людей



double d2n=2/n;
for(i=0;i<m;i++)
{
d2n=дробная_часть_от(d2n*2);
}

остаток=n*d2n;

экскламейшн!  Отлично
Записан

Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 23-07-2004 17:12 » 

хотя нет - гоню Жаль
Цитата

d=2^d


я попутал как d=d^2
Записан

Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #7 : 23-07-2004 20:23 » 

Какое бы это число не было, в двоичной системе оно будет выглядеть как 1 + куча нулей. Количество нулей целиком и полностью будет зависеть от степени двойки в предыдушем месяце. Я полностью не проверял, но мне кажется, что достаточно взять прибыль за любой месяц, так чтобы она была гораздо больше количества людей на данной фирме и проверить остаток деления. И я думаю он будет повторяться для любого месяца.
И чтоб я так жил. За какой-то год я во много богаче Билли. Хочу быть акционером данной фирмы. Archangel, дай пожалуста адрес данной конторы.  Отлично
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Mouse
Молодой специалист

ru
Offline Offline

« Ответ #8 : 26-07-2004 08:02 » 

Алексей1153, спасибо, алгоритм хорош! (правда, не тот, но порцию удовольствия я получил  Отлично )

Finch, взять прибыль за любой месяц просто нельзя, так как к 6-му месяцу прибыль будет 2^65536. Про стабилизацию остатков я уже думал, проверял на количестве учредителей = 1...30. В большинстве случаев остатки стабилизируются, но в некоторых случаях этого не происходит.  Жаль Причем иногда остатки просто чередуются от месяца к месяцу, а иногда разумную закономерность выделить не получается...   Ха-ха-ха

ИМХО должен быть математический алгоритм, что-то из абстрактной алгебры...  :idea:
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #9 : 26-07-2004 11:38 » 

во как... (тут смайлик "чешу репу" (ГРОМ ещё не выложил) - не забыть бы потом сюда вставить...)

Улыбаюсь
Записан

Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 27-07-2004 04:01 » 

Archangel, а вот и решение:

мы, по сути , ищем дробную часть от выражения d(m)/n

заметим такую вещь:
при m=1, d=2,
при m=2, d=(2**2),
при m=3, d=((2**2)**2),

то есть в лесенке степеней - (m-1) двоек

весь прикол в том, что "ряд" (не знаю ещё как назвать Улыбаюсь ) вида

d(m)/n==(...(((2**2)**2)...)**2)/n, где (m-1) степеней

стремится к бесконечности, причем зверски быстро с точки зрения представления чисел в памяти компа. Его надо заменить на квадратный корень (он стремится к единице):

d(m)/n ==((( (2/Q(...Q( Q(n) ))...)**2)**2)...)**2

при возвдении в много степеней двойки воспользуемся формулой:
(a+b)**2 == a**2 + 2*a*b + b**2, где a - целая часть числа, b-дробная.
Так как нас интересует только дробная часть результата, то a**2 отбрасываем, и считаем дальше:
(0 + 2*a*b + b**2)**2  -  и так далее.

считаем так:
Код:

#define n 3 //человеки
#define m 10 //месяцы

double dN,d,a,b;
int i;

//считаем dN=Q)...Q) Q)n: :...:
dN=n;
for)i=1; i<m; i++:
|
    dN=sqrt)dN:;
"

//считаем d=2/dN
d=2/dN;

//считаем d=)...))d**2:**2:...**2:

for)i=1; i<m; i++:
|
    b=дробная_часть_от)d:;
    a=целая_часть_от)d:;
    d=2*a*b+b**2;
"

//считаем остаток N
double N=n*d;



ну и, собственно, округляем N до целого...
Записан

Mouse
Молодой специалист

ru
Offline Offline

« Ответ #11 : 27-07-2004 06:45 » 

Твой код выдает результат = 32, если округлять N до целого. Учитывая, что человеков у нас только 3 штуки, тут что-то не то...  :?

Можно поподробнее, как ты перешел от степеней двойки к квадратным корням? Лучше на простом примере:
d(3)/n==((2**2)**2)/n
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #12 : 27-07-2004 08:11 » 

Archangel, я забыл добавить -

//считаем остаток N
d=дробная_часть_от(d);
double N=n*d;

а ещё я заметил один косяк -
Цитата

при возвдении в много степеней двойки воспользуемся формулой:
(a+b)**2 == a**2 + 2*a*b + b**2, где a - целая часть числа, b-дробная.
Так как нас интересует только дробная часть результата, то a**2 отбрасываем, и считаем дальше:
(0 + 2*a*b + b**2)**2 - и так далее.

это неправильно, целая часть тоже будет влиять на результат... Надо придумать что-то ещё, либо воспользоваться предложенным мною ранее способом
Записан

Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 27-07-2004 08:21 » 

Цитата

Можно поподробнее, как ты перешел от степеней двойки к квадратным корням? Лучше на простом примере:
d(3)/n==((2**2)**2)/n


берём от всего выра корень - два раза, а затем всё возводим в квадрат два раза
Записан

Mouse
Молодой специалист

ru
Offline Offline

« Ответ #14 : 27-07-2004 10:13 » 

Да, теперь понятно, интересный ход. Только вот проблему это не решает...   Так больше нельзя... Бллин, во задачка! Она попалась одной моей знакомой в институте на 2-м (!!!) курсе как курсовая работа. Причем препод сам не знал, как ее решать.  :twisted:
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #15 : 27-07-2004 14:27 » 

Я думаю, я нашел путь решения этой задачи. Правда понадобится очень точная математика после запятой. И человек получше меня разбираюшийся в математике. Но это уже частности. Главное путь.
Для начала пара замечаний.
- Какое-бы не было число, остаток будет всегда меньше количества компаньенов данной компании.
- Так как нельзя тут нарисовать красиво и правильно математические формулы, введем обозначение. Заместо "Логарифм с базой два" буду в дальнейшем писать "Lb".

Свойства логарифма, которые я хочу применить.
Lb(2)=1
Lb(2**2)=2*Lb(2)=2
Lb(A/B) = Lb(A)/Lb(B)
Lb(A*B)=Lb(A)*Lb(B)


Ряд
d(m) = ((...(((2**2)**2)...)**2)-Q)/N, где (m-1) степеней (Как уже упоминалось ранее)
Это количество денег, которые получит компаньен в каждый конкретный месяц.
, где Q и есть остаток, который нам нужно найти.

Вот здесь нужно обмозговать, так чтобы d(m) и это степенное безобразие попали под логарифм, а Q была вынесена за него.
Пока до меня не доходит.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #16 : 27-07-2004 15:18 » 

Lb(2)=1
Lb(2**2)=2*Lb(2)=2
Lb(A/B) = Lb(A)/Lb(B)
Lb(A*B)=Lb(A)*Lb(B)

Finch! Опомнись!
Lb(A/B) = Lb(A)-Lb(B)
Lb(A*B)=Lb(A)+Lb(B)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #17 : 27-07-2004 15:26 » 

Sla, Спасибо за поправку. Но все равно, пока это не дает результат.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #18 : 28-07-2004 04:20 » 

Finch, с логарифмами я пробовал - не получится так. Получится лишь понизить на одно возведение в квадрат

всегда дело упирается в то, что приходится считать некоторое число

B=((((A**2)**2)**2)...)**2

то есть если, к примеру, на ассемблере написать операторы для типа MEGAdouble, который хранит числа с точностью, скажем, 128 знаков, и степень десятки, скажем, 8796093022208, то все проблемы решатся. Месяца эдак до 70-го.

А вообще - фирме негде будет столько хранить средств, и скорее всего их ограбят и разорят. А может они разорятся из-за сложности вычисления дохода.  Отлично
Записан

Mouse
Молодой специалист

ru
Offline Offline

« Ответ #19 : 28-07-2004 07:52 » 

Алексей1153, к теме доходов и расходов. Недавно мой начальник ездил к заказчику одного нашего проекта оговаривать условия оплаты. Стоимость проекта - около миллиона рублей. Так вот, на вопрос о способе оплаты эти юмористы ответили просто - оплачивать будут наличными!  Отлично Хотел бы я посмотреть на такую кипу денег...  Отлично
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #20 : 28-07-2004 07:56 » 

Цитата: Алексей1153
Finch, А вообще - фирме негде будет столько хранить средств, и скорее всего их ограбят и разорят. А может они разорятся из-за сложности вычисления дохода.  Отлично


Гы, а кто-нить вообще смотрел сколько это будет 2^65536?
Да столько денег наверно во всей Галактике на сыщется!!!

А потом, вы не задумывались какие-такие "фирмы" такие доходы дают?
Наркотики? оружие (атомное, хим. и бак.)? Всё вместе, сразу и много!

А понизить степень двойки думаю можно так:

2^(2^m)  = exp(2^m*ln(2))
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #21 : 28-07-2004 15:00 » 

Джон,
Цитата
Гы, а кто-нить вообще смотрел сколько это будет 2^65536?

В двоичной записи возьми дамп памяти на 16 кБайт. Вот Самый старший байт будет равен 128 а все остальные 0. В деятичной системе еше веселее. Это число с 19729 знаками.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #22 : 28-07-2004 15:50 » 

Finch,  Дык и про это же. Калькулятор виндовский правда справился - не загнулся

2,0035299304068464649790723515603e+19728

те типа 10 в степени 19728. Насколько я знаю самое большое число - гугол 10^100 и то нафиг никому не нужно. А тут степень в 197 раз больше. Я шокирован!  :new_shot:
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #23 : 28-07-2004 16:19 » 

Еше одна ветка для размышления. Я тут эксперементировал с числами на малых степенях двойки. И заметил. Остатки циклически повторяются. Вот теперь надо найти на каком шаге цикла будет остаток. И можно ответить на вопрос. Пока я не догнал до конца, как высчитать шаг цикла. С числом 2^65536 вроде проблем не должно возникнуть. Но для числа 2^(2^65536) и выше. Вот тут и начинаются грабли.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #24 : 29-07-2004 08:12 » 

Finch,  Так я не понял, а чем логарифмы не подходят?
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #25 : 29-07-2004 08:31 » 

Так, Джон,
Цитата

2^(2^m) = exp(2^m*ln(2))

это, конечно, позволяет посчитать степень S, но нужно же ещё в эту степень число d возвести
Цитата

//считаем d=(...((d**2)**2)...**2)


а весь прикол в том, что от этого всего нужна только дробная часть результата (причём - как можно точнее), а если просто взять и посчитать, то она потеряется - не хватит значащих цифр
Записан

Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #26 : 29-07-2004 11:26 » 

Господа! придумайте что-нибудь!
Идея такова.
Если число хозяевов кратно 2^ - остаток 0
не кратно - остаток не может быть больше числа хозяевов
У меня не хватает знаков в калькуляторе что бы посчитать 2^65536  Жжешь
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Mouse
Молодой специалист

ru
Offline Offline

« Ответ #27 : 29-07-2004 11:41 » 

Finch, идею с циклическим повторением я уже отбросил. Я просчитал все остатки для количества руководителей N = 1...30. В большинстве случаев закономерность есть, но не всегда. Некоторые числа из закономерности выпадают, но дело даже не в этом. Нам же нужно написать алгоритм, работающий для любого месяца, а если реализовывать закономерности для конкретных чисел, то это будет большой switch {}, что неприемлимо.

Вообще мне почему-то кажется, что при последовательном возведении в степень для нахождения остатка нам не нужно все число, нужна только его часть. Причем эта часть не должна вылезать за границы Int32. ИМХО. Осталось понять, как можно выделить эту часть...  :twisted:  Как думаете, может в этом направлении стоит двигаться?  :?:
Записан
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #28 : 29-07-2004 16:27 » 

Archangel, Цикл то он есть. Только это зависит от длины цикла. Если бы его радимого не было. То тогда можно было бы замастырить генератор случайных чисел. Заметь не псевдослучайных, а имено случайных. А это, как говорят в Одессе, две большие разници.
Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #29 : 29-07-2004 18:05 » 

И еше мне пришла такая мысля. Что если преобразовать число в число с базисом счисления N. Теперь догадайтесь, а что будет остатком деления. Правильно младший разряд. Теперь все остальные разряды нас в принципе не интересуют, а интересует как будет изменяться младший разряд. т.е. программа для числа 2^65536 будет
Код:
int Q=1;       /Остаток
int N=29;     /базис счисления
for (int i=1; i<=65536; i++)
   {
    Q *= 2;
    if (Q>=N) Q -=N;
   }
Для числа 2^65536 оно канечно можно посчитать. А вот дальше думать надобно. Число 2^(2^65536) даже КРЭЙ считать будет миллионы лет.
Джон,
Цитата
Finch, Так я не понял, а чем логарифмы не подходят?
в идеале с логарифмами хотелось бы получить
Lb(.....Lb(Q).......) = X
где Q - это остаток, и X - это конкретное число.
Сколько я не искал формулы преобразования логарифмов, кроме тех которые я с помошью Sla выложил + Преобразование базиса логарифма, честно говоря, я ничего не нашел. Все остальное это частные случаи этих формул. И я еше не нашел путь как достигнуть вышесказанного результата путем преобразования. Поэтому пошел другим путем.
« Последнее редактирование: 29-11-2007 16:06 от Алексей1153++ » Записан

Не будите спашяго дракона.
             Джаффар (Коша)
Страниц: [1] 2 3 4 ... 7   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines