Две цифры. 5 и 9

[faradey]

Сколько n-значных чисел можно составить с помощью двух цифр 5 и 9, в которых три одинаковых цифры не стоят рядом?

Буду благодарен за помощь, можно код или мат. модель.

[danekne]

Комбинаторика. Сколько всего чисел можно составить - 2 в степени N. Потом считаешь, сколько можно в этом числе составить цепочек из трех одинаковых цифр. Разница и будет решением твоей задачи

Ааа, второе н

Ааа блин, вторая часть моего сообщения не совсем верна. Там может быть и больше трех символов цепочки.



_________________
Не используйте форум как чат - не пишите несколько коротких сообщений подряд!
Есть что добавить - нажимайте кнопку "Правка/Редактировать" на своём крайнем сообщении
и изменяйте, добавляйте....

Прошу учесть на будущее...

Модератор.

[Serge_Bliznykov]

а я бы предложил в лоб перебирать варианты, считая те, что подходят (нет трёх одинаковых символов подряд).

p.s. то, что даны цифры 5 и 9 - это вообще НЕ ВАЖНО!
важно то, что это ДВА символа.
поэтому перебирать можно (и нужно) двоичные числа разрядности N, проверяя, что в данном двоичном числе нет подряд трёх нулей или трёх единиц.
написать такое можно за 10 минут...

[faradey]

спасибо большое, если можно насчет первого способа подробней, а насчет второго способа то с двоичной системой я плохо работаю(

п.с. у меня идет подготовка к обласной олимп по программированию 8-11 класс

[Вадим Мошев]

Могу предположить, что это вычисляется по формуле:
2^n - 2*размещения (из n элементов по n-3)

[Serge_Bliznykov]

вот, для затравки решение с перебором вариантов.

Const MaxN = 30;

Type TBinArray = array[1..MaxN] of byte;

function IsRepeatThreeValues(A : TBinArray; ArraySize : byte ) : boolean;
var i, KS : byte;
begin
  IsRepeatThreeValues := false;
  if ArraySize < 3 then Exit;
  KS := 1;
  for i:=2 to ArraySize do
    if A[i]=A[i-1] then begin
        Inc(KS);
        if KS >= 3 then begin
          IsRepeatThreeValues := true;
          Exit;
        end
    end
    else KS := 1;
end;


procedure AddOne(var A : TBinArray; ArraySize : byte );
var i : integer;
  perenos  : byte;
begin
   perenos := 1;
   for i:=ArraySize downto 1 do begin
     A[i] := A[i] + perenos;
     if A[i]>1 then begin
       perenos := 1;
       A[i] := 0;
     end
     else perenos := 0;
   end;
end;        


var
 A : TBinArray;
 N : byte;
 i, MaxCount, Count : longint;

begin
  {ввод числа N}
  WriteLn('введите размерность N (от 1 до 30): ');
  Readln(N);

  {иницилизация N}
  MaxCount := 1;
  for i:=1 to N do begin A[i] := 0; MaxCount := MaxCount shl 1; end;

  Count := 0;
  for i:=1 to MaxCount do begin
    if Not IsRepeatThreeValues( A, N ) then Inc(Count);
    AddOne( A, N );
  end;
  WriteLn(Count);
  Readln
end.

p.s. проверил в online системе http://www.e-olimp.com
по скорости не все тексты проходит.. надо вместо массива использовать обычное число или вообще менять алгоритм решения...

[Fellics{новичок}]

Лучше всего такую задачу знание комбинаторики решит, потому что перебор может по времени не зайти если в систему сдавать

[Serge_Bliznykov]

потому что перебор может по времени не зайти если в систему сдавать

так и есть. перебор по времени не проходит.

[faradey]

спасибо большое))
очень благодарен.
Это конечно нагло, но всеже, если не лень подскажите еще такую

В арифметическом выражении разрешается использовать число 1, и операции:умножения, сумирование и скобки. Какое минимальное количество единиц необходимо чтобы получить заданое натуральное число N.

это похоже на задачу типа возможно ли составить заданую суму с заданой последовательности расставляя +,-; и решается это рекурсивной функцией, но у меня неполучается переделать решение под эту задачу.

[Serge_Bliznykov]

спасибо большое))
очень благодарен.

к сожалению, вынужден признать, что благодарить меня не за что!
Дело в том, что, моё решение с одной стороны - выдаёт правильные результаты,
с другой - решено перебором. А эта задача на ДИНАМИЧЕСКОЕ программирование.
Нужно использовать ДРУГОЙ алгоритм.
если эту задачу сдавать преподавателю - то может прокатит, может не прокатит - зависит от этого преподавателя.
Но если это решение попытаться сдать на любой олимпиаде, то оно завалится на временных ограчениях - решение перебором банально не пройдёт в 1.3 секунду для N=30, например...
нужно кардинально другое решение.
если будет сегодня время - я попытаюсь всё таки ПРАВИЛЬНО решить данную задачу.

Это конечно нагло, но всеже, если не лень подскажите еще такую

В арифметическом выражении разрешается использовать число 1, и операции:умножения, сумирование и скобки. Какое минимальное количество единиц необходимо чтобы получить заданое натуральное число N.

да ни в коем разе! Так нельзя!
то, что Вы пытаетесь сделать - называется КРОССПОСТ!! (плюс ещё и нарушение правила - "Один вопрос - одна тема"

Есть же Ваша же тема:
Единици. Минимальная последовательность.

прошу воздержаться от обсуждения и решения задачи с единичками в данной теме!