| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
К- ричные числа.
Armageddon © (2002-12-10 22:22:00)Дорогие господа программисты. Предлагаю вашему вниманию еще одну задачу.
Требуется вычислить количество N значных чисел в системе счисления с основанием K таких, что их запись не содержит двух подряд идущих нулей. Ограничения 2<=K<=10; N>=2; 4<=N+K<=180(!!!).
Когда-то я очень долго бился над задачей, недавно попалась на глаза. Помогите пожайлуста. Только не предлагайте, пожалуйста, способов типа "заносим в массив и просто проверяем нет ли в нем двух подряд идущих нулей". Необходим действительно рациональный и быстрый алгоритм. Буду очень презнателен.
Uncle Archi (2002-12-13 21:45:00) [1]>Ты наверное писал на Borland Pascal а они компилируют на
>дельфях, отсюда и больше памяти. Я тоже несколькими способами >решал эту задачу, но то ответ не верен, то времени слишком
>много затрачивается на решение :-)
Они компилят на хорошем паскале, который позволяет делать большие массивы и использует много памяти.
// если написать Int64-ошибка компиляции
DarkGreen (2002-12-13 07:10:00) [2]2 Separator © (13.12.02 06:48)
Спасибо большое за пояснения.
Этим парням из университета, надо посоветовать научиться ставить условия задачи. Чтобы люди, учавствующие в конкурсе не ломали себе голову над интерпретацией задания.
Separator (2002-12-13 06:48:00) [3]нет, если больше, то они тоже долны удалятся. Вот рабочий пример, но в acm.timus он не проходит по времени:
function ExStr(N, K: integer): integer; //Для проверки значений
function Proverka(S: string): boolean;
var
i: integer;
begin
Result:= true;
for i:= 2 to Length(S) - 1 do
if (S[i] = "0") and (S[i + 1] = "0") then
begin
Result:= false;
Break
end
end;
var
J: integer;
procedure Work(Level: integer; S: string);
var
i: integer;
begin
if Level = 1 then
for i:= 1 to K - 1 do
Work(Level + 1, IntToStr(i))
else
if Level <> N then
for i:= 0 to K - 1 do
Work(Level + 1, S + IntToStr(i))
else
for i:= 0 to K - 1 do
if Proverka(S + IntToStr(i)) then
Inc(J)
end;
Самый примитивный метод решения задачи, кстати я тоже делал примерно также как и ты, только там формула попроще:
function Ex(N, K: integer): integer;
begin
Result:= trunc(exp(N * ln(K)) - exp((N - 1) * Ln(K)) - (N - 2) * (K - 1))
end;
Но результат не верен, если брать допусти N = 5 и K = 10
DarkGreen (2002-12-13 06:35:00) [4]2 Separator ©:
Ну в этом случае, они конкретные уроды, указывают Паскаль, а компилят делфями, при чем даже компилируя делфями размер программы не может быть 390Кб. :(. Да, на счет этой задачи, как я понял, необходимо исключить из общего количества N-значных чисел, те, которые внутри себя содержат два подряд идущих нуля, а вот что делать, если число подряд идущих нулей > 2, в условии про это ни чего не говорится, и я такие числа не удалял, правильно ли это?
Separator (2002-12-13 06:16:00) [5]
> DarkGreen © (13.12.02 05:43)
Ты наверное писал на Borland Pascal а они компилируют на дельфях, отсюда и больше памяти. Я тоже несколькими способами решал эту задачу, но то ответ не верен, то времени слишком много затрачивается на решение :-)
DarkGreen (2002-12-13 05:43:00) [6]2 Uncle Archi ©: И где ты там увидел 390Кб переменных??? Программа в 100000 на паскале имеет сегмент данных ~64Кб. А у данной программы Data Size = 756 Code Size = 2829 Stack Size = 16384 (Borland Pascal 7.0)
> Значит не решил
Веский аргумент. Ты хотя бы решение глянул?
Uncle Archi (2002-12-12 21:25:00) [7]>После компиляции размер exe"шника составил ~9Кб, а в статиске >мне сказали, что количество используемой памяти = 390 Кб,
>что-то у них там не так работает. Иль я в чем не прав?
Память даётся та, которую занимают переменные, а не exe"шник
>отправли ее на acm.timus.ru, а мне говорят, что решение
>неверное
Значит не решил
DarkGreen (2002-12-12 16:13:00) [8]Дополнение:
После компиляции размер exe"шника составил ~9Кб, а в статиске мне сказали, что количество используемой памяти = 390 Кб, что-то у них там не так работает. Иль я в чем не прав?
DarkGreen (2002-12-12 16:11:00) [9]Страно, у меня получилась следующаая формула (если я правильно понял условия задачи) Result := K^n-K^(n-1)-(n-2)*(K-1), написал программульку бытренько, отправли ее на acm.timus.ru, а мне говорят, что решение неверное. Вот мое решение:
program K_N;
function Ex(K1, N1: Integer): Longint;
var
I: Integer;
Res: Longint;
begin
Res := K1;
for I := 1 to N1 - 1 do
begin
Res := Res * K1;
end;
Ex := Res;
end;
var
K, N: Integer;
Result: Longint;
begin
ReadLn(N, K);
Result := Ex(K, N)-Ex(K, N-1)-(N-2)*(K-1);
WriteLn(Result);
end.
Uncle Archi (2002-12-12 12:27:00) [10]Зайди на
acm.timus.ru
Armageddon (2002-12-10 23:00:00) [11]Между прочем эта задача была придложена в прошлом году на областной олимпиаде. А что точно такую задачу предложил кто-то еще я не виноват.
Uncle Archi (2002-12-10 22:34:00) [12]Это нечестно! Решать задачи с Timus"a при помощи других!
(Задача № 1009 ссылка:
http://acm.timus.ru/problem.asp?id=1009&rus)
| |
