Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.67
konstr81
0 / 0 / 0
Регистрация: 29.08.2009
Сообщений: 3
#1

Задача "Кузнечик" - C++

30.08.2009, 00:17. Просмотров 3232. Ответов 4
Метки нет (Все метки)

Помогите решить в С++ задачу про цифрового кузнечика: имеется линейный массив из 20 чисел 1,2,3,4...20. По нём может прыгать кузнечик скачками по 2 и по 3 клетки. Нужно создать программку, которая считает сколько есть вариантов у кузнечика попасть из клетки 0 на клетку 20. Использовать цикл "for"...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.08.2009, 00:17     Задача "Кузнечик"
Посмотрите здесь:

Мелодия "В траве сидел кузнечик" с помощь спецификаторов - C++
Нужно написать исходник на Visual C++!! ----------------------------------------------- Вивести в консоли после компиляции мелодию...

Из pascal в c++. "Кузнечик" - C++
помогите переделать код из паскаля в с++ var N,i,j,K:integer; a:array of longint; begin write('N= '); read(N); write('K=...

Вычислить значение суммы. Задача с использованием "длинной арифметики". - C++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...

Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" - C++
Здравствуйте! Не могу решить задачу из книги. Задача Введите целые данные, содержащие только нули и единицы (т.е. «двоичные»...

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером - C++
Гигабашня — самое высокое и глубокое здание в Киберленде. В ней 17 777 777 777 этажей, пронумерованных от  - 8 888 888 888 до...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт С++
8284 / 3503 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
30.08.2009, 00:40     Задача "Кузнечик" #2
такой вопрос вариант
0 2 2 3 3 2 2 2 2 2
и
0 2 2 2 3 2 2 3 2 2
считаются одним вариантом или нет?
Жестянка
сцуко киборг
102 / 29 / 2
Регистрация: 11.09.2008
Сообщений: 193
30.08.2009, 02:28     Задача "Кузнечик" #3
Всё давольно просто. Тебе надо посчитать количество комбинаций из нескольких двоек и троек, сумма которых равна 20. тоесть есть выражение с двумя неизвестными: 2х+3у=20.
выражаем:

3у = 20 - 2x
y = (20 - 2x)/3


При этом есть условие, что х и у должны быть целыми.

Поэтому цыкел должен выглядеть примерно так:
C++
1
2
for(x=0;x<=20;x++)
      {if((20 - 2x)/3&1==0)k++;}
(k - счетчик подходящих комбинаций.)

как-то так. :-)

Добавлено через 4 минуты
это если не учитывается последовательность 2 и 3.

если учитывается, то, узнав у при каждом х, внутри цикла подсчитываем количество возможных комбинаций методами мат.стата

ща листинг накатаю...

Добавлено через 31 минуту
та-а-ак... количество возможных перестановок: A = n(n-1)(n-2)...(n-m+1)
n - количество эллементов т.е. x+y
m - количество возможных вариантов т.е. 2 (двойка или тройка)

Значить еще один for
C++
1
2
3
4
dk=1;
for(slog=0;slog<=3;slog++)
     {dk = dk * (x + y - slog);}
k+=dk;
и того:

C++
1
2
3
4
5
6
7
8
9
10
11
12
k=0;
for(int x=0;x<=20;x++)
      {
      y = (20 - 2x)/3;
      if(y&1==0)
           {
           dk=1;
           for(int slog=0;slog<=3;slog++)
                 {dk = dk * (x + y - slog);}
           k+=dk;
           } 
      }
konstr81
0 / 0 / 0
Регистрация: 29.08.2009
Сообщений: 3
30.08.2009, 10:26  [ТС]     Задача "Кузнечик" #4
Цитата Сообщение от M128K145 Посмотреть сообщение
такой вопрос вариант
0 2 2 3 3 2 2 2 2 2
и
0 2 2 2 3 2 2 3 2 2
считаются одним вариантом или нет?

Не считаются
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.08.2009, 21:06     Задача "Кузнечик"
Еще ссылки по теме:

Структуры... Задача: "База сотрудников небольшой фирмы" - C++
По каждому сотруднику вводится следующая информация: • Фамилия, имя, отчество; • год и дата рождения; • пол; • стаж работы по...

Задача "Гонки по улицам" (обход ориентированного графа) - C++
Здравствуйте,помогите с задачей,если можно с комметарием,чтобы разобраться.Спасибо На рисунке ниже изображен пример плана улиц для гонки....

Задача из книги "Програмирование - принципы и практика использования C++" - C++
Кто читал ету книгу, помогите разобратся с задачей с 12 главы. Никак не могу скомпилировать простую программу. Вот ее код: #include...

Задача "Движение по клеткам таблицы" (Динамическое программирование) - C++
Хотел узнать, может у кого-нибудь в архивах есть подобная задача, которую можно будет использовать как шаблон к моей. Есть таблица NxM,...

Задача "Максимальный подпалиндром" не могу поймать ошибку. - C++
Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Подпалиндромом данной строки называется...

Создать класс Account. Задача из книги Дейтелов "Как програмировать на С++" - C++
Начал изучение С++, прочитал главу &quot;Введение в классы и объекты&quot; в книге Дейтелов &quot;Как програмировать на С++&quot;, ничего не поняв прочитал её...


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

Или воспользуйтесь поиском по форуму:
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
30.08.2009, 21:06     Задача "Кузнечик" #5
Все решается в один проход методом динамического программирования.
Прыгать будем с конца - то есть сначала с 20 клетки на 20-ую.
Потом с 19-ой на 20-ой. И так далее.
Считаем что с 20-ой на 20-ую нам требуется один прыжок.
Массив сделаем немного больше, но справа от 20 напишем нули.
Это чтобы не контролировать что прыжок перепрыгивает за 20-ую клетку

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
#include <stdio.h>
 
#define N 20
#define N0 (1+N+3)
 
int main( void ) {
 
int i, k;
int var[N0];
 
 
for ( i= 0; i<N0; i++ ) { var[i]= 0; }
 
var[N]= 1;
for ( k= N-1; k>=0; k-- ) {
    var[k]= var[k+2]+var[k+3];
}
 
printf( "index variants\n" );
for ( i= N; i>=0; i-- ) {
    printf( "%5d %5d\n", i, var[i] );
}
 
return 0;
 
} /* main() */
Вывод программы:
Код
> grig.exe
index variants
   20     1
   19     0
   18     1
   17     1
   16     1
   15     2
   14     2
   13     3
   12     4
   11     5
   10     7
    9     9
    8    12
    7    16
    6    21
    5    28
    4    37
    3    49
    2    65
    1    86
    0   114
Yandex
Объявления
30.08.2009, 21:06     Задача "Кузнечик"
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru