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

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

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

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

30.08.2009, 00:17. Просмотров 3082. Ответов 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++
Строка: заменить первую "о" на "а", удалив остальные "о" C++
Все слова, не содержащие "bc" и заканчивающиеся на "ad" заменить на "!" C++
C++ Двусвязный список с объектом трех типов: "целое число", "вещественное число", "строка"
C++ Дана точка на плоскости с координатами (х, у). Составить программу, которая выдает одно из сообщений "Да", "Нет", "На
Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером C++
C++ Необработанное исключение в "0x104b2288" в "Matrix.exe": 0xC0000005: Нарушение прав доступа при записи "0xcdcd
Из pascal в c++. "Кузнечик" C++
Из слова "яблоко" путем склеек и вырезок его букв получить слова "блок" и "око" C++
Поменять знак " $ " на " * " к первому вхождению символа " ? " C++
C++ Задача на нахождение "+" и "-" элементов в массиве
C++ Необработанное исключение в "0x0138169d" в "kursovaya.exe": 0xC0000005: Нарушение прав доступа при чтении "0x6

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
M128K145
Эксперт C++
8280 / 3499 / 143
Регистрация: 03.07.2009
Сообщений: 10,707
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
считаются одним вариантом или нет?

Не считаются
odip
Эксперт С++
7153 / 3293 / 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     Задача "Кузнечик"
Ответ Создать тему
Опции темы

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