Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

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

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

Даны три слова - "мама", "мыла", "раму". Задача - напечатать всевозможные варианты построения слов - C++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

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

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - C++
Разработать программу с использованием наследования классов, реализующую классы: − воин; − пехотинец(винтовка); − матрос(кортик). ...

4
M128K145
Эксперт С++
8297 / 3517 / 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
считаются одним вариантом или нет?
0
Жестянка
сцуко киборг
103 / 30 / 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;
           } 
      }
0
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
считаются одним вариантом или нет?

Не считаются
0
odip
Эксперт С++
7159 / 3221 / 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
0
30.08.2009, 21:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.08.2009, 21:06
Привет! Вот еще темы с ответами:

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

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Определить тип данных "Запись", имеющий поля "Фамилия", "Пол", "Зарплата" - C++
определить тип данных запись имеющий поля фамилия пол зарплата. определить массив из 10 записей. в программе ввести в массив данные и...


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

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

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