2 / 2 / 0
Регистрация: 03.05.2020
Сообщений: 199
1

Без двух нулей подряд

20.06.2021, 13:41. Показов 7417. Ответов 14
Метки нет (Все метки)

Требуется посчитать количество последовательностей длины n, состоящих из цифр от 0 до k−1 таких, что никакие два соседних элемента последовательности не равны нулю одновременно.

Входные данные

Заданы два натуральных числа N и K (2≤K≤10; 2≤N; 4≤N+K≤18).

Выходные данные

Необходимо вывести целое число — ответ на задачу.

Примеры
Ввод
2 2
Вывод
3
Ввод
3 9
Вывод
712
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.06.2021, 13:41
Ответы с готовыми решениями:

Генерировать все цепочки из 0 и 1 длины n, в которых нет двух нулей подряд
Цепочки из 0 и 1. Генерировать все цепочки из 0 и 1 длины n, в которых нет двух нулей подряд. Число...

Удаление двух или более подряд стоящих нулей в одномерном динамическом массиве
Привет всем :) Помогите исправить программу. Нужно удалить из одномерного динамического массива два...

Определить сколько имеется чисел таких что в их записи не содержится более двух подряд идущих нулей
Задача: среди всех чисел в системе счисления с основанием к(2<=k<=10) определить сколько имеется...

Заменить в массиве все группы подряд расположенных нулей на значение количества нулей
Ввести массив, который содержит много нулевых элементов. Заменить все группы подряд расположенных...

14
583 / 487 / 370
Регистрация: 05.11.2013
Сообщений: 1,262
Записей в блоге: 6
20.06.2021, 16:24 2
Другими словами, нужно вычислить количество n-значных чисел в системе счисления с основанием k, таких что их запись не содержит двух подряд идущих нулей.
Если k здесь - основание системы счисления, при k = 10 и n = 3 имеем, например, всего 900 трёхзначных чисел, убираем из списка 100, 200, ..., 900, получаем 891, как на моём тесте.
А логика такая, что d1 - это количество чисел, состоящих ровно из i цифр и оканчивающихся на цифру, отличную от нуля, а d0 - количество i-значных чисел, оканчивающихся на нуль.
Так как по условию n больше 1, числа с лидирующими нулями не рассматриваем даже при i = 1, поэтому даём начальные значения d1 = k - 1, d0 = 0.
Потом выражаем d1, d0 через их предыдущие значения в цикле от 2 до n включительно, рассматривая только те числа, которые не содержат в своей записи двух нулей подряд.

Только чот 712 не выходит для 3 и 9

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
 
int main() {
 const int n = 3, k = 10;
 int d1 = k - 1, d0 = 0, d;
 for (int i = 2; i <= n; i++) {
  d = d1;
  d1 = (d1 + d0)*(k - 1);
  d0 = d;
 }
 cout << d1 + d0;
 return 0;
}
0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 03:47 3
Лучший ответ Сообщение было отмечено ПерС как решение

Решение

Цитата Сообщение от dmitrii2000 Посмотреть сообщение
Требуется посчитать количество последовательностей длины n, состоящих из цифр от 0 до k−1 таких, что никакие два соседних элемента последовательности не равны нулю одновременно.
Если мысленно добавить к нашей последовательности два воображаемых ненулевых элемента: один в начале, а другой в конце

Код
    |------------- n -------------|
[*] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ][*] 
 ^                                  ^
 воображаемый                       воображаемый
то любое легальное ("несоседнее") расположение z нулей в нашей исходной последовательности длины n будет соответствовать разбиению числа n+2-z на z+1 положительных слагаемых (с учетом порядка).

Например, для n=8 такое расположение нулей

Код
[*] [ ] [0] [ ] [ ] [ ] [0] [ ] [ ][*]
Соответствует разбиению числа 10 на слагаемые 2+3+3.

Количество таких разбиений, как известно, равно https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{(n+2-z)-1}^{(z+1)-1}, то есть https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n-z+1}^z. Например для n=8 и z=2 получаем https://www.cyberforum.ru/cgi-bin/latex.cgi?C_7^2 = 21 вариантов легального размещения двух нулей.

В каждом разбиении с z нулями у нас будет n-z ненулевых элементов, то есть у нас будет https://www.cyberforum.ru/cgi-bin/latex.cgi?{(k-1)}^{n-z} вариантов расположения этих ненулевых элементов. Таким образом, ответ задачи - это сумма по всем возможным количествам нулей z

https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{z=0}^{n} C_{n-z+1}^z \cdot {(k-1)}^{n-z}


Не стараясь оптимизировать особо:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
 
unsigned long long C(unsigned m, unsigned n)
{
  if (m > n)
    return 0;
 
  unsigned long long num = 1;
  for (unsigned mul = n; mul > m; --mul)
    num *= mul;
 
  unsigned long long den = 1;
  for (unsigned mul = n - m; mul > 1; --mul)
    den *= mul;
 
  return num / den;
}
 
unsigned long long int_pow(unsigned a, unsigned b)
{
  unsigned long long result = 1;
 
  for (; b != 0; b >>= 1, a *= a)
    if ((b & 1) != 0)
      result *= a;
 
  return result;
}
 
int main() 
{
  unsigned n = 3, k = 9;
 
  unsigned long long total = 0;
  for (unsigned z = 0; z <= n; ++z)
    total += C(z, n - z + 1) * int_pow(k - 1, n - z);
 
  std::cout << total << std::endl;
}
Код
712
Разумеется, совсем не обязательно суммировать аж до z <= n. Понятно, что как только количество нулей становится больше n/2 + 1, правильно разместить нули становится невозможно и слагаемые становятся равны 0.

Добавлено через 1 час 44 минуты
Цитата Сообщение от ПерС Посмотреть сообщение
Только чот 712 не выходит для 3 и 9
Bash
1
2
$ awk 'BEGIN { for (a = 0; a < 9; ++a) for (b = 0; b < 9; ++b) for (c = 0; c < 9; ++c) print a b c }' | grep -v 00 -c
712
4
583 / 487 / 370
Регистрация: 05.11.2013
Сообщений: 1,262
Записей в блоге: 6
21.06.2021, 03:57 4
Первая программа (моя) не считает числа с лидирующими нулями.
Например, при n = 4, k = 2
2-я программа говорит 8
у меня 5
0000
0001
0010
0011
0100
0101
0110
0111

1000
1001
1010
1011

1100
1101
1110
1111


n = 2, k = 10
2-я программа говорит 99
у меня 90, 10..99
но если считаем 1..9, то как раз 99

так что несколько разные задачи получаются, если длина цепочки точно равна n, то да, второй вариант!
0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 04:01 5
Цитата Сообщение от ПерС Посмотреть сообщение
Первая программа (моя) не считает числа с лидирующими нулями.
Ну то есть ваша программа неправильна - она не решает поставленную задачу.

Цитата Сообщение от ПерС Посмотреть сообщение
так что несколько разные задачи получаются, если длина цепочки точно равна n, то да, второй вариант!
Задача тут только одна - описанная в вопросе.
0
ПерС
21.06.2021, 04:09
  #6

Не по теме:

Ну и пусть не решает. Она решает другую задачу.
А что от гуру тут за все старания доброго слова не дождёшься - я привык :)

0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 06:05 7
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
[...]Соответствует разбиению числа 10 на слагаемые 2+3+3.[...]
Вкралась опечатка. Имелось в виду: "Соответствует разбиению числа 8 на слагаемые 2+3+3".
0
2 / 2 / 0
Регистрация: 03.05.2020
Сообщений: 199
21.06.2021, 06:12  [ТС] 8
Программа выдаёт неверный ответ
0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 06:49 9
Цитата Сообщение от dmitrii2000 Посмотреть сообщение
Программа выдаёт неверный ответ
Вы о чем вообще? Какая "программа"? Какой "неверный ответ"?
0
2 / 2 / 0
Регистрация: 03.05.2020
Сообщений: 199
21.06.2021, 07:56  [ТС] 10
Ваша программа не верная
0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 08:26 11
Цитата Сообщение от dmitrii2000 Посмотреть сообщение
Ваша программа не верная
Не надо выдумывать. Программа абсолютно верная.

Если вам кажется, что она неверная - то давайте сюда примеры входных данных, на которых моя программа дает неправильный результат. А без этого - не нужно замусоривать тему бессмысленными сообщениями.
0
4813 / 2273 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
21.06.2021, 12:47 12
Лучший ответ Сообщение было отмечено dmitrii2000 как решение

Решение

Или "народной" динамикой ака мемоизацией
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n, k;
 
unsigned long long d[50][1];
 
unsigned long long f (int i, int l) {
    if (i == 0) return 1;
    if (!d[i][l]) d[i][l] = (l ? 0 : f(i-1, 1)) + (k-1)*f(i-1, 0);
    return d[i][l];
}
 
int main() {
    std::cin >> n >> k;
    std::cout << f(n, 0);
}
Добавлено через 29 минут
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
давайте сюда примеры входных данных
у вас переполнение uint_64 из-за
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Не стараясь оптимизировать особо:
а ТС ниасилил это понять

Добавлено через 3 минуты
а
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
давайте сюда примеры входных данных
он не может, потому что его тестирующая система пишет только "Неправильный ответ в тесте № 5"
2
583 / 487 / 370
Регистрация: 05.11.2013
Сообщений: 1,262
Записей в блоге: 6
21.06.2021, 13:08 13
супер
просто интересно стало, заглянул в конце рабочего дня ещё раз... тьфу уже на эту задачу... ну всё, вот так еще попробую и всё )
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
unsigned long long g(int, int);
 
unsigned long long f (int n, int k) {
 if (n == 1) return k;
 return (k - 1) * (f(n - 1, k) + g(n - 1, k));
}
 
unsigned long long g(int n, int k) {
 if (n == 1) return 1;
 return f(n - 1, k);
}
 
int main() {
 cout << f(2, 2) << endl; //3
 cout << f(2, 10) << endl; //99
 cout << f(3, 9) << endl; //712
 cout << f(3, 10) << endl; //981
 cout << f(9, 9) << endl; //353603584
 return 0;
}
0
С чаем беда...
Эксперт CЭксперт С++
9979 / 5333 / 1459
Регистрация: 18.10.2014
Сообщений: 12,818
21.06.2021, 16:58 14
Цитата Сообщение от _Ivana Посмотреть сообщение
у вас переполнение uint_64 из-за
На каких входных данных (учитывая диапазоны, приведенные в условии задачи)?

Цитата Сообщение от _Ivana Посмотреть сообщение
а ТС ниасилил это понять
ТС, скорее всего, "ниасилил понять" то, что в моей программе не сделан ввод входных параметров и тупо засунул ее в тестовую систему в первозданном виде, где она радостно выдавала 712 в ответ на все входы. А сюда он валил чушь, про "программа не верная".
0
4813 / 2273 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
21.06.2021, 19:42 15
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
На каких входных данных (учитывая диапазоны, приведенные в условии задачи)?
Да, не обратил внимание, что там ограничения совсем децкие, не оба аргумента по отдельности до 18 а их сумма. Переполнение, например, при n = 16, k = 16, но это выходит за рамки ограничений. Тут и моя динамика не нужна, можно однострочник сделать.

Пожалуй, разделю ваше предположение по поводу ТС
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.06.2021, 19:42
Помогаю со студенческими работами здесь

Матрица L(n,k) состоит из нулей и единиц. Найти в ней самую длинную цепочку подряд стоящих нулей по горизонтал
Помогите решить на C++ QtCreator

Есть код, нужно чтобы остановка программы была после ввода двух нулей подряд, а не после одного
Помогите, очень прошу. Есть код, нужно чтобы остановка программы была после ввода двух нулей...

Определить количество нулей в десятичной записи числа без учета нулей в младших разрядах
Дано число N (N&gt;9) определить количество нулей в записи числа, кроме нулей в младших разрядах...

функция. количество идущих подряд нулей.
Помогите пожалуйста написать эту функцию=.=

В двоичном числе определить количество соседств двух нулей и двух единиц
Нужна помощь в написании кода на C++. Буду очень благодарен Дано короткое целое неотрицательное...

Работа с битами, вывести на экран все комбинации двух единиц и двух нулей
Здравствуйте, не могу решить такую задачу: К примеру есть 4 бита: 1010. Нужно функция которая...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru