Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.12.2018, 14:22   #1
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию Ошибка в алгоритме Флавия

Привет всем! Задача Флавия.
Цитата:
Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам
Делаю так:
Код:
int flav3 (int n, int k) {
	
	vector<int> wars[n];

	// Инициализация массива
    for (int i=0; i<=n; ++i) {
        
        wars->push_back (i);    
    }
    
    int uk=k;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars->erase(wars->begin() + uk);
    }
    
    // Результат
    return wars->front();
}
Но результат отличается от правильного
Еким вне форума Ответить с цитированием
Старый 10.12.2018, 14:42   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,694
По умолчанию

Цитата:
Сообщение от Еким Посмотреть сообщение
vector<int> wars[n];
Массив векторов?

Цитата:
Сообщение от Еким Посмотреть сообщение
for (int i=0; i<=n; ++i) {
n+1 элемент?

Цитата:
Сообщение от Еким Посмотреть сообщение
int uk=k; // Удаляемый элемент
Т.е. первого подходящего пропускаем?

Цитата:
Сообщение от Еким Посмотреть сообщение
while (n>1) {
Два же должны остаться.
p51x вне форума Ответить с цитированием
Старый 10.12.2018, 14:48   #3
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию

Спасибо за замечания!
Код:
Два же должны остаться.
Задача в общем виде, и преподаватель сказал, что всегда должен оставаться 1 У меня есть рабочий пример с Википедии, там тоже один остается...
Еким вне форума Ответить с цитированием
Старый 10.12.2018, 14:52   #4
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию

Я исправил
Код:
int flav3 (int n, int k) {
	
	vector<int> wars;

	// Инициализация массива
    for (int i=0; i<n+1; ++i) {
        
        wars.push_back (i);    
    }
    
    int uk=0;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars.erase(wars.begin() + uk);
        uk=uk-1;
    }
    
    // Результат
    return wars.front();
}
Добавил в конце вычитание указателя на 1. Я плохо представляю процесс, но думаю я когда удаляю элемент в векторе должен и уменьшать указатель на 1 - массив же уменьшился. Или нет?. Контрольный пример для n=5. k=2 (ответ 3) теперь проходит. Но остальные примеры нет.
Еким вне форума Ответить с цитированием
Старый 10.12.2018, 14:57   #5
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию

Вот я дурак! Оказывается не проходит. Я не правильно инициализировал вектор!
Вставил вывод вектора на экран.
Код:
int flav3 (int n, int k) {
	
	vector<int> wars;

	// Инициализация массива
    for (int i=0; i<n+1; ++i) {
        
        wars.push_back (i+1);    
    }
    
    int uk=0;                    // Удаляемый элемент
    while (n>1) {
        
        
        // Найдем позицию удаляемого элемента
        uk=uk+k;
        
        // Вышли за границу массива?
        if (uk > n-1){
            
            // Вычтем массив
            uk=uk-n;
        }
       
        // Оставшиеся элементы
        n=n-1;
        
        // Удаляем элемент
        wars.erase(wars.begin() + uk);
        
        for (int i=0; i<=wars.size(); ++i) {
            
            cout<<wars[i]<<" ";
        }
        
        cout<<"\n";
    }
    
    // Результат
    return wars.front();
}
В общем алгоритм работает не правильно.
Еким вне форума Ответить с цитированием
Старый 10.12.2018, 15:19   #6
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,694
По умолчанию

Код:
int flav3 (int n, int k) {
	std::vector<int> wars;
	// Инициализация массива
    for (int i=0; i<n; ++i) {
        wars.push_back(i);
    }
    
    int uk = 0;
    while (wars.size()>1) {
    	uk=(uk+k-1)%wars.size();
        wars.erase(wars.begin() + uk);
        for (auto& e : wars) {
            std::cout << e << ' ';
        }
        std::cout << '\n';
    }
    
    // Результат
    return wars.front();
}
пробуйте
p51x вне форума Ответить с цитированием
Старый 10.12.2018, 15:34   #7
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию

Да, это работает!
Что значит
Код:
for (auto& e : wars)
?
Вот я знал, что где-то нужно двигать указатель удаляемого элемента:
Код:
uk=(uk+k-1)%wars.size();
Только я никак не мог понять где его нужно двигать для расчета.
Еким вне форума Ответить с цитированием
Старый 10.12.2018, 15:39   #8
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,694
По умолчанию

https://en.cppreference.com/w/cpp/language/range-for
p51x вне форума Ответить с цитированием
Старый 10.12.2018, 15:43   #9
Еким
Новичок
Джуниор
 
Регистрация: 10.12.2018
Сообщений: 6
По умолчанию

Нас такому не учили .
Но https://www.onlinegdb.com проглатывает.
Спасибо большое! Тему можно считать исчерпанной!
Еким вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ошибка в алгоритме шифрования NekoDead Visual C++ 3 24.10.2018 17:54
ошибка в алгоритме с++ Tavasilyok Помощь студентам 1 29.05.2016 19:55
Ошибка в алгоритме parkito Общие вопросы C/C++ 1 07.12.2011 04:25
Ошибка в алгоритме поиска murzilka6002 Общие вопросы C/C++ 15 24.11.2011 04:57
Ошибка в алгоритме слияние массивов ATAMAN200 Общие вопросы C/C++ 3 25.10.2010 20:37