На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
15 мая "Исходники.РУ" отмечают 20-летие присутствия в сети!
Поздравляем всех причастных и неравнодушных с юбилеем сайта!
И огромное спасибо всем, кто был с нами все эти годы!
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Делители
    Как найти число(минимальное) по заданному к-ву делителей?
    Например для 3 - 4,для 4 – 6, для 6 -12, для 5-16 и т. д.
    З.Ы. перебор желательно не использовать(если перебор, то быстрый)
    [move]Эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи.[/move]
      Во первых ты не получишь однозначного решения. Так как, например чисел с 3 делителями много (4, 9 и т.п. в основном все квадраты и прочие степени чисел). Аналогично и с другими числами.  
      Подпись была выключена в связи с наложенным наказанием.
      Да ну и фиг с ней
        2GrAnd:
        Человек русским языком просит МИНИМАЛЬНОЕ число :)
        Благодарности отослать мылом, пиво, цветы и поклонниц - в аттаче.
          Не думайте что я тут выпендрился и забыл, я усиленно размышляю над задачей... Блин, все мозги уже свернул а к ответу почти и не приблизился :) Ессно, я ищу математическое решение без всякого перебора.
          Благодарности отослать мылом, пиво, цветы и поклонниц - в аттаче.
            Вот-вот, математическое мне как раз нужно... ???
            [move]Эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи.[/move]
              Надеюсь мозги мои выдержат и я решу. Ждите... Но на меня сильно не надейтесь, у меня ещё куча всякой гадости вроде задания по матану.
              Сообщение отредактировано: HOMO_PROGRAMMATIS -
              Благодарности отослать мылом, пиво, цветы и поклонниц - в аттаче.
                Эта задача была на областной Владимирской олимпиаде по информатике среди школьников сего года.
                Я эту задачу не решил, то есть решил, но использовал перебор (в этой задаче "быстрого" перебора не существует).
                Поэтому решать можно только математикой....


                Для начала сделаем два замечания. Во-первых, пусть некоторое число М разложено на простые множители, т.е. М = Пpidi.Тогда число различных его делителей, включая 1 и М, можно вычислить по формуле П(di+1). Для решения поставленной задачи необходимо, чтобы это выражение было равно N. Во-вторых, если с учетом первого замечания подобрать такие di, чтобы М было минимальным, то решением данной задачи будет М = 2d13d25d37d411d5
                После этих двух замечаний легко видеть, что данная задачи решается следующим образом: сначала необходимо перебрать все разбиения числа N на множители (их при заданных ограничениях будет не больше 9), затем для каждого разбиения определить di, и по ним вычислить М, и, наконец, выбрать среди полученных М минимальное.
                PS. N - число делителей, M - искомое число.
                Сообщение отредактировано: albom -
                Убилбытого,ктосломалмойпробел!
                  To albom:
                  Слушай, нафига разбивать N на множители ??? Ведь не обязательно у N и M будут общие делители  :) и только не говори мне, что из твоей формулы M=..... при различных d1,d2,d3 всегда будет M с кол-вом делителей, равным N.(если ты хочешь определять d1,d2,d3 ,то перебор будет ещё больше) ; хотя может я чего-то недопонял?....

                  P.S. У нас тоже эта задача на областной была. "Шоу" называлась. Я решил перебором, но, по-моему, перебор не решение...(у тебя нет решения с олимпиады? )...
                  [move]Эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи.[/move]
                    Всё-всё, допёрло до пенька(т.е. до меня)! Если кто парится из-зи меня, то Вы уж простите.

                    To albom:
                         N:=(d1+1)*(d2+1)*(d3+1)…(di+1);
                         И если N так разложить, то из твоей формулы М всегда будет иметь ровно N делителей;
                         теперь как сделать, чтобы М было минимальным: во-первых, d1>=d2;d2>=d3…;
                         во-вторых, i (т.е. кол-во множителей 2*3*5*7*11…) зависит от di, например:
                         2^3=8(N=4,N=(3+1)*(0+1)… ),или 2^1 * 3^1 =6(N=4,N=(1+1)*(1+1)*(1+0))

                    Хотя, можно можно получить все М и выбрать минимальное…
                         
                    [move]Эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи.[/move]
                      Рассмотрим алгоритм на примере, когда N=24.
                      Итак, раскладываем число N на простые множители: 24=2*2*2*3.
                      Так как всего множителей только 4, то берем первые 4 простых числа: 2, 3, 5, 7. Теперь нам нужно подобрать нужные показатели степеней к этим числам, причем показатели степени должны быть такими, что если прибавить к каждой к ним по единице, а потом перемножить их, то произведение будет равно 24.
                      Теперь можно начинать перебор (на самом деле здесь не много вариантов).
                      Возьмем такие степени 23, 0, 0, 0 (действительно (23+1)*(0+1)*(0+1)*(0+1)=24), тогда мы получаем число 223+30+50+70=8388608. Хм, большое число, но у него ровно 24 делителя. В этом этапе мы решили, что 24=24*1*1*1.
                      Теперь у нас есть такой вариант, что 24=8*3*1*1. Тогда мы получаем степени (8-1), (3-1), 0, 0.
                      Подставляем их, получаем: 27+32+50+70=1152. Получили меньшее число, запомним его.
                      Теперь пора сделать маленькое замечание, т.к. простые числа идут у нас в порядке возрастания, то показатели степеней должны не возрастать. Т.е. случай, когда 24=3*8 (и показатели степеней равны 2, 7, 0, 0) не рассматривается.
                      Теперь подумаем, как еще можно разложить число 24 на множители? Ага, можно попробовать так: 24=12*2*1*1. Тогда показатели степеней равны 11, 1, 0, 0. И мы получаем число  211+31+50+70=6144 - явно не лучший вариант.
                      Далее по аналогии:
                      24=6*4*1*1, степени 5, 3, 0, 0, число: 25+33+50+70=864.
                      24=6*2*2*1, степени 5, 1, 1, 0, число: 25+31+51+70=525.  
                      24=4*3*2*1, степени 3, 2, 1, 0, число: 23+32+51+70=360.
                      24=3*2*2*2, степени 2,1, 1, 1, число: 22+31+51+71=420.
                      И дальше делаем аналогично.

                      Ну и в конце мы стоим перед не очень сложной задачкой:
                      Какое число из 8388608,  6144, 1152, 864, 525, 360, 420.... и т.д. наименьшее?
                      Ну, конечно же, 360, это и есть ответ к задаче.
                      Убилбытого,ктосломалмойпробел!
                        ExpandedWrap disabled
                          uses crt;
                          var n,n0:word;
                              mn:array[1..128]of comp;
                              pr:array[1..256]of longint;
                              c:word;
                              i:word;
                              min:comp;
                          function power(a,b:comp):comp;
                           var r:comp;
                           begin
                           r:=1;
                           while b>0 do
                            begin
                            r:=r*a;b:=b-1;
                            if r>=9.2e18/a then begin power:=0;exit end;
                            end;
                           power:=r;
                           end;
                          procedure test(num:byte);
                           var r,z:comp;
                               k:byte;
                           begin
                           r:=1;
                           for k:=1 to num do
                            begin
                            z:=power(pr[k],mn[k]-1);
                            if z=0 then exit;
                            r:=r*z;
                            if r>=min then exit;
                            end;
                           min:=r;
                           end;
                           
                          procedure build(ind:byte;nn:word);near;
                           var d:word;
                           begin
                           if nn=1 then
                            begin
                            test(ind-1);
                            exit;
                            end;
                           for d:=2 to nn do
                            begin
                            if (ind>1)and(mn[ind-1]<d)then break;
                            if nn mod d=0 then
                             begin
                             mn[ind]:=d;
                             build(ind+1,nn div d);
                             end;
                            end;
                           end;
                          label zzz;
                          begin
                          clrscr;
                          c:=1;
                          pr[1]:=2;
                          i:=3;
                          while c<256 do
                           begin
                           for n:=1 to c do
                            if i mod pr[n]=0 then
                             goto zzz;
                           inc(c);
                           pr[c]:=i;
                           zzz:
                           inc(i,2);
                           end;
                          min:=9.2e18;
                          writeln('Введите кол-во делителей');
                          readln(n);
                          build(1,n);
                          if min=9.2e18 then
                           writeln('Число с таким количеством делителей больше чем 9.2*10^18 !')
                           else
                           writeln('Минимальное число, у которого ровно ',n,' делителя: ',min:0:0);
                          readkey;
                          end.
                        Убилбытого,ктосломалмойпробел!
                          Ну вот и я про то же!  :D  :D

                          зы спасибо  ;)
                          [move]Эстетическая прелесть программы - это не архитектурное излишество, а то, что отличает в программировании успех от неудачи.[/move]
                          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                          0 пользователей:


                          Рейтинг@Mail.ru
                          [ Script Execution time: 0,1203 ]   [ 16 queries used ]   [ Generated: 31.05.20, 22:26 GMT ]