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

задача: какая банка останется последней? - C++

Восстановить пароль Регистрация
 
ITTI
0 / 0 / 0
Регистрация: 02.01.2012
Сообщений: 25
04.04.2012, 14:28     задача: какая банка останется последней? #1
есть n банок, при первом подходе разбивают первую сначала банку и затем каждую вторую, при втором подходе первую не разбитую и каждую третью не разбитую и т.д. какую банку разобъют последней?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2012, 14:28     задача: какая банка останется последней?
Посмотрите здесь:

C++ Выводить строку, сокращая каждый раз на 1 символ, пока в строке не останется 1 символ
Разрешено ли и возможно ли программисту написать приложение для работы с процессинговым центром Банка? C++
Моделирование очереди банка C++
C++ Вычислить остаток счета депозита банка
Сколько букв останется на своих местах в данной строке, ес¬ли ее символы записать в обратном порядке C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
04.04.2012, 14:49     задача: какая банка останется последней? #2
каждую третью последнюю не разбитую. элементарно
ITTI
0 / 0 / 0
Регистрация: 02.01.2012
Сообщений: 25
04.04.2012, 15:04  [ТС]     задача: какая банка останется последней? #3
Цитата Сообщение от lazybiz Посмотреть сообщение
каждую третью последнюю не разбитую. элементарно
ок, всего банок, к примеру, 42, так какая последней будет разбита?
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
04.04.2012, 15:17     задача: какая банка останется последней? #4
последней будет 41-я
ITTI
0 / 0 / 0
Регистрация: 02.01.2012
Сообщений: 25
04.04.2012, 15:40  [ТС]     задача: какая банка останется последней? #5
Цитата Сообщение от lazybiz Посмотреть сообщение
последней будет 41-я
нет, 42 и будет последней.
если 9 банок, то 6.
если 314, то 282.
есть какие-то другие предположения?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
04.04.2012, 15:42     задача: какая банка останется последней? #6
А ограничения на n какие? Можно ведь просто смоделировать, если ограничения позволяют.
ITTI
0 / 0 / 0
Регистрация: 02.01.2012
Сообщений: 25
04.04.2012, 15:48  [ТС]     задача: какая банка останется последней? #7
Цитата Сообщение от diagon Посмотреть сообщение
А ограничения на n какие? Можно ведь просто смоделировать, если ограничения позволяют.
1<n<10 000 000. позволяют?)
zss
Модератор
Эксперт С++
 Аватар для zss
5949 / 5554 / 1785
Регистрация: 18.12.2011
Сообщений: 14,193
Завершенные тесты: 1
04.04.2012, 15:54     задача: какая банка останется последней? #8
Если я правильно понял условие задачи, то алгоритм такой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int n=42;
int count=n;
int banki[n];
for(int i=0;i<count;i++)
  banki[i]=i+1;
while(count)
{
    for(int i=0;i<count-1;i++)//прошлись по всем банкам
    {
        for(int j=i;j<count) // удалили очередную четную банку
              banki[j]=banki[j+1];
        count--;
    }
}// повторяем пока есть банки
cout<<banki[0]; // это последняя
ITTI
0 / 0 / 0
Регистрация: 02.01.2012
Сообщений: 25
04.04.2012, 16:38  [ТС]     задача: какая банка останется последней? #9
Цитата Сообщение от zss Посмотреть сообщение
Если я правильно понял условие задачи, то алгоритм такой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int n=42;
int count=n;
int banki[n];
for(int i=0;i<count;i++)
  banki[i]=i+1;
while(count)
{
    for(int i=0;i<count-1;i++)//второй раз i=1, следовательно и j
    {
        for(int j=i;j<count) // зачем этот цикл, если он повторяется один раз?
              banki[j]=banki[j+1];//и вот тут тогда пропускается banki[0]
        count--;
    }
}// повторяем пока есть банки
cout<<banki[0]; // это последняя
в любом случае каждая первая банка разбивается.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.04.2012, 16:51     задача: какая банка останется последней? #10
Цитата Сообщение от ITTI Посмотреть сообщение
какую банку разобъют последней?
можно шуткой: первую (ведь она на момент разбивания стоит на первом месте). На самом деле решение при таких ограничениях только одно:
Сначало считать количество оставшихся целых банок после каждого битья. Потом отталкиваясь от оставшегося количества восстанавливать номер банки в обратную сторону. Можно учесть еще вот такой момент:
Допустим осталось 9 банок, и мы должны разбить каждую 8. Разбиваем каждую восьмую остается 8 банок. Далее разбиваем первую банку - остается 7 банок. Далее мы должны разбить каждую 9 банку - вот тут можно остановиться. Ведь разобьется теперь последней та банка, которая сейчас последняя (седьмая).
Я на примере
Цитата Сообщение от ITTI Посмотреть сообщение
если 9 банок, то 6.
объясню как я бы решал. Итак имеем 9 банок.
1. Разбиваем 1-ую. остается 8.
2. Разбиваем каждую вторую. Остается 4.
3. Разбиваем 1-ую. Остается 3.
4. Разбиваем каждую 3. Остается 2.
5. Разбиваем 1-ую. Остается 1. (я специально остановился именно на этом пункте, а не на предыдущем). Здесь останавливаемся. Потому что нужно разбивать каждую 4-ую, а у нас банок меньше.
Итак имеем 1 банку и число 3 (последний раз разбивали каждую 3-ю), идем обратно:
- 1+1=2 (это обратная операция п.5). Т.е. наша банка после этой операции стала второй
- Т.к. разбивали каждую 3-ю, а наша оставшаяся банка только 2-я, то она и останется 2-ой.
- 2+1=3 (это обратная операция п.3). Т.е. наша банка после этой операции стала второй
- Т.к. разбивали каждую 2-ую банку, а наша банка 3, то наша банка становится 5.
- 5+1=6 (это обратная операция п.1)
Ответ: 6.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2012, 23:48     задача: какая банка останется последней?
Еще ссылки по теме:

Алгоритм: Как определить размера банка? C++
Обнулять по очереди максимальный и минимальный элементы массива, пока не останется последний. C++
C++ Из последовательности удалять каждый K-ый элемент до тех пор, пока не останется одно число

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

Или воспользуйтесь поиском по форуму:
castaway
Эксперт С++
4848 / 2987 / 368
Регистрация: 10.11.2010
Сообщений: 11,028
Записей в блоге: 10
Завершенные тесты: 1
04.04.2012, 23:48     задача: какая банка останется последней? #11
Цитата Сообщение от ITTI Посмотреть сообщение
в любом случае каждая первая банка разбивается.
... и вторая.
А вообще, условие, которое ты поставил, заслуживает звания "Самое безграмотное постановление задачи 2012".
Yandex
Объявления
04.04.2012, 23:48     задача: какая банка останется последней?
Ответ Создать тему
Опции темы

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