Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите решить задачу. / 22 сообщений из 22, страница 1 из 1
16.12.2013, 21:40
    #38502754
DimOnline
DimOnline
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
Даны два четырёхзначных числа A и B. Выведите в порядке возрастания все четырёхзначные числа в интервале от A до B, запись которых содержит ровно три одинаковые цифры.
Ввод Вывод
1900 1911
2100 1999
        2000
        2022
 
=Моё решение#include <iostream>

using namespace std;

int main()
{
long long a,b,i;
cin>>a>>b;
for(i=a;i<=b;i++)
{
if((i/1000==i%1000/100&&i%1000/100==i%100/10)||(i/1000==i%1000/100&&i%1000/100==i%10)||(i/1000==i%100/10&&i%100/10==i%10)||(i%10==i%1000/100&&i%1000/100==i%100/10))
{
cout<<i<<" ";
}
}
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2013, 21:41
    #38502755
DimOnline
DimOnline
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnline,

Моё решение очень плохое, занимает много памяти,очень не акуратное, и работает лишь при 6 проверках из 20. Хотелось бы узнать как такие задачи решать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2013, 22:02
    #38502785
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnlineDimOnline,

Моё решение очень плохое, занимает много памяти,очень не акуратное, и работает лишь при 6 проверках из 20. Хотелось бы узнать как такие задачи решать.
Шаг 1: Сначала решаешь эту задачу на бумажке. Потом решаешь ее на бумажке для другой пары исходных цифр. Потом для третей....
Шаг 2: Когда поймешь что именно ты делаешь при решении на бумажке - записываешь эту последовательность действий. На другую бумажку записываешь. Это черновик алгоритма.
Шаг 3: Потом берешь все свои исходные пары цифр и повторяешь поиск решений подчиняясь черновику алгоритма.
Шаг 4: Почти всегда результаты третьего шага не будут совпадать с результатами первого. Пытаешь понять почему произошло несовпадение. Либо ты ошибся на первом шаге, либо ошибка в алгоритме. Если ошибка в алгоритме исправляешь ее и повторяешь третий шаг.
Шаг 5: Если уверен что алгоритм правильный - включаешь компьютер и записываешь алгоритм на нужном/любимом/каком-нибудь языке программирования.
Шаг 6: Прогоняешь полученную программу по всем тем парам цифр которые ты использовал в первом и третьем шаге. Если есть разница в результатах - где-то ошибка. Либо в алгоритме и тогда ты выключаешь компьютер и прыгаешь на шаг 3. Либо в переводе алгоритма на ЯП - прыгаешь на шаг 5.

Ни в коем случае не начинай процесс решения задач со включения компьютера.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2013, 22:04
    #38502787
DimOnline
DimOnline
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
White OwlDimOnlineDimOnline,

Моё решение очень плохое, занимает много памяти,очень не акуратное, и работает лишь при 6 проверках из 20. Хотелось бы узнать как такие задачи решать.
Шаг 1: Сначала решаешь эту задачу на бумажке. Потом решаешь ее на бумажке для другой пары исходных цифр. Потом для третей....
Шаг 2: Когда поймешь что именно ты делаешь при решении на бумажке - записываешь эту последовательность действий. На другую бумажку записываешь. Это черновик алгоритма.
Шаг 3: Потом берешь все свои исходные пары цифр и повторяешь поиск решений подчиняясь черновику алгоритма.
Шаг 4: Почти всегда результаты третьего шага не будут совпадать с результатами первого. Пытаешь понять почему произошло несовпадение. Либо ты ошибся на первом шаге, либо ошибка в алгоритме. Если ошибка в алгоритме исправляешь ее и повторяешь третий шаг.
Шаг 5: Если уверен что алгоритм правильный - включаешь компьютер и записываешь алгоритм на нужном/любимом/каком-нибудь языке программирования.
Шаг 6: Прогоняешь полученную программу по всем тем парам цифр которые ты использовал в первом и третьем шаге. Если есть разница в результатах - где-то ошибка. Либо в алгоритме и тогда ты выключаешь компьютер и прыгаешь на шаг 3. Либо в переводе алгоритма на ЯП - прыгаешь на шаг 5.

Ни в коем случае не начинай процесс решения задач со включения компьютера.
Так я уже все перепроверил, с моей точки зрения решение правильное, но затратное, а говорят совсем наоборот.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2013, 22:25
    #38502798
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnline,

Хохо... 6 из 20.. Это что, олимпиада какая? :)

Итак, как всегда, решать в лоб - это не круто :) Потому и такие решения получаются не лучшим образом.

А алгоритм такой. сначала уйдём от наших A и B и разберёмся как получить все числа удовлетворяющих условию, что в них 3 одинаковых цифры.
то есть, если мы заменим одинаковые цифры на 1, а отличающуюся на 0, то получим, что такое число должно подходить под один из шаблонов:
1110 1101 1011 0111

таких чисел всего по 36 на каждую цифру, потому всего их 360.

Как в правильном порядке их перебрать, идей пока нету...
но, если мы запустим цикл от 0 до 9 (это для наших повторяющихся чисел), вложим в него ещё один от 0 до 9 (это для отличающийся цифры), а в него вложим цикл от 0 до 3 (а это наше расположение отличающийся цифры). В итоге мы сможем перебрать все варианты и выбрать те, которые нам подходят.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
int* arr = new int[360];
unsigned char count = 0;
int chisl0 = 0;
int a, b;
cin>>a>>b;

for(unsigned char rep=0; rep<=9; rep++){
  for(unsigned char no_rep=0; no_rep<=9; no_rep++){
      if(no_rep==rep) continue;
      for(unsigned char place=0; place<4; place++){
        chislo=rep*1111-rep*pow(10, place)+no_rep*pow(10, place);
        if(chislo>a and chislo<b){
          arr[count]=chislo;
          count++;
        }
      }
  }
}



Всё, массив подходящих нам чисел готов... сортируем любым удобным способом по возрастанию и получаем готовый ответ. Над сортировкой посижу, подумаю... может что в голову придёт интересное.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
16.12.2013, 22:35
    #38502805
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnlineТак я уже все перепроверил, с моей точки зрения решение правильное, но затратное, а говорят совсем наоборот.Значит ты не сделал первые три шага.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 09:55
    #38503099
DimOnline
DimOnline
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
ПрограмёрDimOnline,

Хохо... 6 из 20.. Это что, олимпиада какая? :)

Итак, как всегда, решать в лоб - это не круто :) Потому и такие решения получаются не лучшим образом.

А алгоритм такой. сначала уйдём от наших A и B и разберёмся как получить все числа удовлетворяющих условию, что в них 3 одинаковых цифры.
то есть, если мы заменим одинаковые цифры на 1, а отличающуюся на 0, то получим, что такое число должно подходить под один из шаблонов:
1110 1101 1011 0111

таких чисел всего по 36 на каждую цифру, потому всего их 360.

Как в правильном порядке их перебрать, идей пока нету...
но, если мы запустим цикл от 0 до 9 (это для наших повторяющихся чисел), вложим в него ещё один от 0 до 9 (это для отличающийся цифры), а в него вложим цикл от 0 до 3 (а это наше расположение отличающийся цифры). В итоге мы сможем перебрать все варианты и выбрать те, которые нам подходят.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
int* arr = new int[360];
unsigned char count = 0;
int chisl0 = 0;
int a, b;
cin>>a>>b;

for(unsigned char rep=0; rep<=9; rep++){
  for(unsigned char no_rep=0; no_rep<=9; no_rep++){
      if(no_rep==rep) continue;
      for(unsigned char place=0; place<4; place++){
        chislo=rep*1111-rep*pow(10, place)+no_rep*pow(10, place);
        if(chislo>a and chislo<b){
          arr[count]=chislo;
          count++;
        }
      }
  }
}



Всё, массив подходящих нам чисел готов... сортируем любым удобным способом по возрастанию и получаем готовый ответ. Над сортировкой посижу, подумаю... может что в голову придёт интересное.
Дело в том, что задача должна решаться только циклами for,while,until и условиями, массивами пользоваться нельзя.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 10:08
    #38503118
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnline,

ну на мой взгляд чем писать зубодробительные if ы лучше уж перевести число в десятичный вид и в лоб поверить условия.

но это непрогрессивный вариант решения.
прогрессивный дал программёр.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 12:54
    #38503390
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnline,

Странное ограничение ). А в условии задачи оно есть? Ну там же должно быть тогда что-то типа "количество используемой памяти не должно превышать ..."
Или там так и написано "не используя массивы"? Если да, значит какая-то неправильная у Вас олимпиада или что это такое (уж на скольких я побывал - ни разу такого не видел ).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 19:49
    #38504209
DimOnline
DimOnline
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
Програмёр,

Ну понимаешь, эта задача идет в 3-ем переоде в списке базового обучения (1-ый условие иф, 2-ой цикл while, 3-ий цикл for, и 4-ый уже массивы.) по идеи,мы их знать не должны.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 20:15
    #38504230
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnlineПрограмёр,

Ну понимаешь, эта задача идет в 3-ем переоде в списке базового обучения (1-ый условие иф, 2-ой цикл while, 3-ий цикл for, и 4-ый уже массивы.) по идеи,мы их знать не должны.

но ведь ты их уже знаешь? )) так почему бы их не пользовать в программе и не написать приложение используя все требуемые возможности языка используя оптимальный алгоритм. Например, если числа будут не 4-значными, а 5-ти - тогда для прохода по всем числам потребуется 90000 итераций. А в моём случае всего 10*10*5=500... То есть каждая новая цифра прибавляет всего 100 итераций, а не увеличивает число проходов в 9 раз :)

ну а сортировка... методом быстрой сортировки. Учитывая что массив почти полностью отсортирован изначально, количество итераций опять же будет приближённым к log(n)*n, где n - количество элементов. То есть при 500 (это если 5 цифр) это будет приблизительно 1000-1500 итераций.

Ну считайте, общее преимущество моего алгоритма по времени около 4.5 раз... и с каждой цифрой возрастает в разы
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 20:23
    #38504237
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
Давайте решим задачу в общем случае. Есть n-значные числа (диапазон).
Вывести в порядке возрастания всё в интервале от A до B, запись которых
содержит ровно m одинаковых цифр.

Дополнительное ограничение.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:25
    #38504287
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
mayton,

Слишком просто :)

Код: plaintext
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.
27.
28.
bool has_dup_digits(int num, int digit_num, int dup_num)
{
    int digits[10] = {};
    int max_dum_num = 0;

    for (int i = 0; i < digit_num; ++i) {
        int digit = num % 10;
        if (++digits[digit] > max_dum_num)
            max_dum_num = digits[digit];
        num /= 10;
    }
    return max_dum_num == dup_num;
}

void gen_nums(int start, int end, int digit_num, int dup_num)
{
    for (int i = start; i <= end; ++i) {
        if (!has_dup_digits(i, digit_num, dup_num))
            continue;
        cout << setfill('0') << setw(digit_num) << i << endl;
    }
}

int main()
{
    gen_nums(1900, 2100, 4, 3);
    return 0;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:29
    #38504290
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
Anatoly Moskovsky, давай уберём ограничение в int. Наиболее пузатые
косяки алгоритма вылезают внезапно на объёмах превышающих
наши скромные ожидания.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:41
    #38504304
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
mayton,

Давайте. Ждем ваш вариант :)

А мне лично лень и некогда думать над генерацией радужной таблицы для такой функции.
Да и не факт, что генерация будет быстрее брутфорса.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:45
    #38504308
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
В некотором более интересном варианте (когда числа выводить не нужно а нужно
просто посчитать количество) мы могли бы учесть количество сочетаний.
Или расширнив рассуждения о сочетаниях перейти к генератору без
брутфорса.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:47
    #38504312
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
maytonДавайте решим задачу в общем случае. Есть n-значные числа (диапазон).
Вывести в порядке возрастания всё в интервале от A до B, запись которых
содержит ровно m одинаковых цифр.

Дополнительное ограничение.



)) мой алгоритм в пролёте, так как тогда надо избавляться от массива, ведь увеличение m-n на единицу приводит к увеличению массива более чем в 10 раз... то есть при m=5 и n=2 он должен быть на 10*999*5!/2!=600*999= чуть меньше чем 600 000 элементов, при чём с повторениями (так как m-n>n), которые отсеять не так легко

Так что... сижу, думаю :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:47
    #38504315
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
mayton,

Я могу и без расчета сочетаний сразу перейти к генерации. Но лень :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 21:49
    #38504318
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
Anatoly Moskovsky, я вас понимаю. Признаюсь что мне тоже лень.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
17.12.2013, 22:03
    #38504331
Програмёр
Програмёр
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
maytonВ некотором более интересном варианте (когда числа выводить не нужно а нужно
просто посчитать количество) мы могли бы учесть количество сочетаний.
Или расширнив рассуждения о сочетаниях перейти к генератору без
брутфорса.

уже посчитал :) 10!/(10-m+n)*m!/n! (без учёта нижней и верхней границы)

это я первым делом сделал, когда предложили более сложную задачу решить )) итак, если m=5, а n=2 мы получаем 43200 подходящих под описание чисел (если я не ошибся конечно). Вопрос в том, как их генерить в правильном порядке :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
18.12.2013, 06:55
    #38504516
m_Sla
m_Sla
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
DimOnlineDimOnline,

Моё решение очень плохое, занимает много памяти,очень не акуратное, и работает лишь при 6 проверках из 20. Хотелось бы узнать как такие задачи решать.Протестировал 3 варианта сравнения.
Код: plaintext
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.
27.
int count=0;
    int a,b,c,d;

    for( a=0; a<10; a++)
        for( b=0; b<10; b++)
            for( c=0; c<10; c++)
                for( d=0; d<10; d++)
                {
                    // Вариант (1)
                    //if((a==b && b==c) ||
                    //   (a==b && b==d) ||
                    //   (a==c && c==d) ||
                    //   (b==c && c==d)
                    //   )

                    // Вариант (2)
                    if((a==b) && (a==c || a==d) ||
                       (c==d) && (a==c || c==b))


                    // Вариант (3)
                    //if( ((a-b) | ((a-c)*(a-d)) ) * ((c-d) | ((a-c)*(c-b)) ) == 0)
                    {
                        count++;
                        cout<<count<<" "<<a<<b<<c<<d<<endl;
                    }
                }

1-й вариант самый медленный.
2-й самый быстрый.
3-й незначительно уступает 2-му (всего одно сравнение, но расчет достаточно ресурсоемкий)
Но это будет сильно зависит от компилятора.

ИМХО самый быстрый вариант с массивом заранее рассчитанных значений:
Код: plaintext
1.
2.
3.
4.
    int nums[]= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                 ...
                 9990, 9991, 9992, 9993, 9994, 9995, 9996, 9997, 9998, 9999
                };
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.12.2013, 00:08
    #38515588
Lepsik
Lepsik
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите решить задачу.
задача похожа на bucket sort. отсортируейте числа по позициям. будет 4 корзинки с индексами.

после этого все выводится элементарно. O(n)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите решить задачу. / 22 сообщений из 22, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]