VPF::Удаление чисел последовательности, которые стоят н

Sahon

Дата 7.4.2011, 22:11 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 14.3.2011
Где: Украина

Репутация: нет
Всего: нет

Задача Del. Дано ряд последовательных натуральных чисел от n до m, из которого удаляют сначала все числа, которые стоят на непарных местах, и так делают до тех пор, пока не останется одно единственное число. Напишите программу, которая найдет это число.

Технические условия. Программа Del читает с клавиатуры числа n и m через пропуск (n<m<1000000). Программа выводит на экран единственное искомое число.

Код


#include <iostream>
using namespace std;
 
int main() {
    int n, m, num=0, a, counter =0;
    cout << "Введите N\n";
    cin >> n;
    cout << "Введите M\n";
    cin >> m;
    const int size = m - n+1;
    int mas[size];
    for (int i = 0; n <= m; i++, n++) {
        mas[i] = n;
        cout << mas[i] << " ";
    }
  while (mas[1])
        {
                for (a = 0; a < size; a++)
                        {
                        if (a % 2) mas[a] = 0;
                        else
                                {
                                if (mas[a] == 0) continue;
                                else 
                                        {
                                        counter++;
                                        mas[a-counter]=mas[a];
                                        mas[a]=0;
                                        }
                                }
                        }
                counter = 0;
        }
        cout << mas[0];
        system ("pause");
        return 0;
}

В чем моя ошибка?

JackYF

Дата 7.4.2011, 22:32 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 6
Всего: 162

Отладчиком пробовали?

--------------------

Пожаловаться на меня как модератора можно здесь.

Sahon

Дата 7.4.2011, 23:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 14.3.2011
Где: Украина

Репутация: нет
Всего: нет

Цитата(JackYF @ 7.4.2011, 22:32

)

Отладчиком пробовали?

Если честно, то я не сильно хорошо умею им пользоваться (вообще не умею). Но алгоритм вроде правильный, да и массив тоже.

volatile

Дата 8.4.2011, 00:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Тут отладчик пока еще не нужен

Цитата(Sahon @ 7.4.2011, 22:11

)

    cout << "Введите M\n";
    cin >> m;
    const int size = m - n+1;
    int mas[size];

так не скомпилируется.
Размер массива должет быть компайл-тайм констант.

ps:Задачка вроде ничо, чуть попозже напишу чо-нибудь (щас занят), если никто не напишет до меня.

Цитата(Sahon @ 7.4.2011, 22:11

)

которые стоят на непарных местах

а что такое непарные? может имелось ввиду нечетные ???

Silent

Дата 8.4.2011, 09:45 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

я бы решил эту задачу совсем другим образом, без массивов:

Код


#include <stdio.h>

typedef unsigned int uint;
uint n, m;

//за пояснением к функции отсылаю к Г.Уоррену, "Алгоритмические трюки для программистов", стр.59
uint flp2(uint x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    return x - (x >> 1);
}

int main()
{
    scanf("%d %d",&n,&m);
    printf("%d", (n-1+flp2(m-n+1)));
    return 0;
}

volatile

Дата 8.4.2011, 13:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Silent, мыслите верно! (хотя ваша программа и неверна).
Здесь вообще не нужен массив, тем более в условии есть подсказка

Цитата(Sahon @ 7.4.2011, 22:11

)

(n<m<1000000).

Мульон элементов!!! задачка видимо из старых времен, когда массив из мульона был невозможен, да и в наше время мульон элементов это очень не хило!
А если учесть еще и цикл по мульону элементов! smile

Задачка решается гораздо быстрее и без бешенных затрат памяти и времени.
если посмотреть после 1-го прохода останутся числа:
0,2,4,6,8,10,12,14,16,18, ...
после 2-го прохода:
0,4,8,12,16, ...
после 3-го:
0,8,16, ...
в общем, после n проходов остаются числа
pow(2,n)*k, где k целое 0,1,2,3...
Короче, объясняльщик из меня плохой. Вот функция, возвращает номер оставшегося элемента, по входным (n,m)

Код


unsigned int residual_elem(unsigned int n, unsigned int m)
{
   unsigned int res = 0;
   for(unsigned int mask = -1; (n-1 & mask) != (m & mask); mask <<= 1)
      res = m & mask;
   return res;
}

Задачка понравилась.

Silent,
n=4 m=15 правильный ответ: 8, ваша программа выдает 11 ?
n=3 m= 7 правильный ответ: 4, ваша программа выдает 6 ?
и т.д.

Sahon

Дата 8.4.2011, 20:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 14.3.2011
Где: Украина

Репутация: нет
Всего: нет

volatile, спасибо большое. Задачка олимпиадная (прошлогодняя) для 9 класса. Вот из-за недостатка знаний не совсем понимаю ход ваших мыслей.

Полный код, как я понял, должен выглядеть примерно так:

Код


#include <iostream>
using namespace std;

unsigned int residual_elem(unsigned int n, unsigned int m);

int main()
{
    unsigned int n, m;
    cout << "Введите N\n";
    cin >> n;
    cout << "Введите M\n";
    cin >> m;
    residual_elem(n, m);
    system ("pause");
    return 0;
}
    
unsigned int residual_elem(unsigned int n, unsigned int m)
{
   unsigned int res = 0;
   for(unsigned int mask = -1; (n-1 & mask) != (m & mask); mask <<= 1)
      res = m & mask;
   return res;
}

Sahon

Дата 8.4.2011, 21:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 14.3.2011
Где: Украина

Репутация: нет
Всего: нет

Код


#include <iostream>
using namespace std;
unsigned int residual_elem(unsigned int n, unsigned int m);
int main()
{
    unsigned int n, m;
    cout << "Введите N\n";
    cin >> n;
    cout << "Введите M\n";
    cin >> m;
    cout << residual_elem(n, m);
    system ("pause");
    return 0;
}
    
unsigned int residual_elem(unsigned int n, unsigned int m)
{
   unsigned int res = 0;
   for(unsigned int mask = -1; (n-1 & mask) != (m & mask); mask <<= 1)
      res = m & mask;
   return res;
}

Это сообщение отредактировал(а) Sahon - 8.4.2011, 22:23

volatile

Дата 8.4.2011, 23:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Ну вобщем-то да, где-то так. Ну, если уж быть совсем педантичным

Цитата(Sahon @ 7.4.2011, 22:11

)

Программа Del читает с клавиатуры числа n и m через пропуск

то надо читать через пропуск (имеется ввиду пробел видимо.) smile

Код


int main()
{
    unsigned int n, m;
    cout << "Введите N, M\n";
    cin >> n >> m;
    cout << residual_elem(n, m) << '\n';
    system ("pause");
    return 0;
}

Sahon

Дата 9.4.2011, 12:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 18
Регистрация: 14.3.2011
Где: Украина

Репутация: нет
Всего: нет

volatile, еще раз спасибо. Но вот можете ли вы сам алгоритм объяснить мне, а то я не совсем понимаю ход ваших мыслей?

volatile

Дата 9.4.2011, 23:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

смысл программы найти в диапазоне [n..m] число, в состав которого входит наибольшее ко-во двоек.
В двоичном представлении это равносильно числу с большим количесвом нулей в конце.
в начале берется маска (-1) - это все единицы, и на каждом шаге сдвигается влево.
по шагам:
11111111111111111111111111111111
11111111111111111111111111111110
11111111111111111111111111111100
11111111111111111111111111111000
11111111111111111111111111110000
эта маска накладывается на n и m и числа сравниваются. Как только они стали равны, маска вышла за диапазон [n..m], берем предпоследнее полученное число, оно у нас в res, это и будет число с максимальным количеством нулей в конце, находящееся в диапазоне [n..m]

ps: Это двочная арифметика, Не забивайте голову. Для новичков, наверное нужно было привести какое-то более наглядное решение, хоть и не такое быстрое. Но у меня решение такое.. ( может быть кто-нибудь даст более понятное решение? )

Silent

Дата 11.4.2011, 12:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Видимо, я не так понял условие задачи. Что такое - "на непарных местах"?
Мое понимание задачи (n=4, m=15):

Строим последовательность:
4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
вычеркиваем на нечетных позициях:
4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 -> 5, 7, 9, 11, 13, 15
повторяем шаги с новой последовательностью:
5, 7, 9, 11, 13, 15 -> 7, 11, 15
7, 11, 15 -> 11

т.е. итеративное удаление из последовательности элементов на нечетных местах

volatile

Дата 12.4.2011, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85

Цитата(Silent @ 11.4.2011, 12:40

)

Видимо, я не так понял условие задачи. Что такое - "на непарных местах"?

Silent, а возможно вы и правы smile

Тут с условиями, действительно не вполне понятно. и еще есть ли нулевой элемент, или счет у них начитается с 1?
Оставим это на совести составителей/переводчиков задания...
Ну, да ладно, проехали smile

Silent

Дата 12.4.2011, 12:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9

Sahon, уважаемый, поясните нам задачу, а вообще б великолепно - процитировать речь организаторов олимпиады с разбора задач.
В интернете я нашел http://www.cyberforum.ru/cpp-beginners/thread268470.html, где создателем аналогичной темы неким Sahon'ом дается пояснение задачи. Я процитирую, (хотя без явного "да, тот товарищъ - я" "нашего" Sahon'а это всего лишь очередной домысел):

Цитата

n и m - натуральные. Программа сама должна заполнить массив чисел от n до m. Например, 1 и 6:
1 2 3 4 5 6
удаляется 1 3 5, то есть массив: 2 4 6 0 0 0, затем удаляется 2 и 6, то есть массив: 4 0 0 0 0 0 и выводиться 4.

И в этом свете получается - моя правота.

Мое мнение - нужно слово Sahon'а.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »