ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Помогите решить задачу.
22 сообщений из 22, страница 1 из 1
Помогите решить задачу.
    #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:40
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38502755
DimOnline
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DimOnline
Гость
DimOnline,

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

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

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

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

Ни в коем случае не начинай процесс решения задач со включения компьютера.
Так я уже все перепроверил, с моей точки зрения решение правильное, но затратное, а говорят совсем наоборот.
...
Рейтинг: 0 / 0
16.12.2013, 22:04
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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:25
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38502805
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
DimOnlineТак я уже все перепроверил, с моей точки зрения решение правильное, но затратное, а говорят совсем наоборот.Значит ты не сделал первые три шага.
...
Рейтинг: 0 / 0
16.12.2013, 22:35
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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, 09:55
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38503118
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
DimOnline,

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

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

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

Ну понимаешь, эта задача идет в 3-ем переоде в списке базового обучения (1-ый условие иф, 2-ой цикл while, 3-ий цикл for, и 4-ый уже массивы.) по идеи,мы их знать не должны.
...
Рейтинг: 0 / 0
17.12.2013, 19:49
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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:15
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504237
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте решим задачу в общем случае. Есть n-значные числа (диапазон).
Вывести в порядке возрастания всё в интервале от A до B, запись которых
содержит ровно m одинаковых цифр.

Дополнительное ограничение.
...
Рейтинг: 0 / 0
17.12.2013, 20:23
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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:25
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504290
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly Moskovsky, давай уберём ограничение в int. Наиболее пузатые
косяки алгоритма вылезают внезапно на объёмах превышающих
наши скромные ожидания.
...
Рейтинг: 0 / 0
17.12.2013, 21:29
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504304
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
mayton,

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

А мне лично лень и некогда думать над генерацией радужной таблицы для такой функции.
Да и не факт, что генерация будет быстрее брутфорса.
...
Рейтинг: 0 / 0
17.12.2013, 21:41
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504308
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В некотором более интересном варианте (когда числа выводить не нужно а нужно
просто посчитать количество) мы могли бы учесть количество сочетаний.
Или расширнив рассуждения о сочетаниях перейти к генератору без
брутфорса.
...
Рейтинг: 0 / 0
17.12.2013, 21:45
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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:47
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504318
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly Moskovsky, я вас понимаю. Признаюсь что мне тоже лень.
...
Рейтинг: 0 / 0
17.12.2013, 21:49
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38504331
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
maytonВ некотором более интересном варианте (когда числа выводить не нужно а нужно
просто посчитать количество) мы могли бы учесть количество сочетаний.
Или расширнив рассуждения о сочетаниях перейти к генератору без
брутфорса.

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

это я первым делом сделал, когда предложили более сложную задачу решить )) итак, если m=5, а n=2 мы получаем 43200 подходящих под описание чисел (если я не ошибся конечно). Вопрос в том, как их генерить в правильном порядке :)
...
Рейтинг: 0 / 0
17.12.2013, 22:03
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #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
18.12.2013, 06:55
| Ответить | Цитировать | Написать  
Помогите решить задачу.
    #38515588
Lepsik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lepsik
Участник
задача похожа на bucket sort. отсортируейте числа по позициям. будет 4 корзинки с индексами.

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


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