Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
TheTimickRus
0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 20
1

Найти наименьший делитель числа Х, который в двенадцатеричной системе состоит из одинаковых цифр

17.03.2018, 11:51. Просмотров 161. Ответов 8
Метки нет (Все метки)

Всем привет!
Вот на учебе задали задачу, но никак не могу решить ее.


Как она звучит полностью:
Найти наименьший делитель числа Х, который в двенадцатеричной системе состоит из одинаковых цифр (если их нет, вернуть 0).

Для начала - вот то, что я смог написать:
Кликните здесь для просмотра всего текста
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "iostream"
 
using namespace std;
 
int MinDivisor(int n);
 
int main()
{
    setlocale(LC_ALL, "");
 
    int n;
 
    cout << " Введите число X и нажмите Enter: "; cin >> n;
    cout << "\n--------------------------\n Ответ: " << MinDivisor(n);
    
    cin.get(); cin.get();
    return EXIT_SUCCESS;
}
 
bool isOnesNumber(int n) // Проверяем, одинаковые ли цифры в числе
{
    int t1 = 0, t2 = n % 10;
    while (n != 0)
    {
        t1 = n % 10;
        if (t1 != t2)
        {
            return false;
        }
        n = n / 10;
        t2 = t1;
    }
    return true;
}
 
int MinDivisor(int n) // Находим наименьший делитель
{
    bool f;
    int div = 0, i = n / 2;
 
    while (i > 1)
    {
        f = true;
        if (n % i == 0 && i / 12 == 0)
            if (isOnesNumber(i))
                div = i;
 
        i--;
    }
 
    return div;
}

А вот примеры работы:
Кликните здесь для просмотра всего текста
Ввод - 25, вывод - 5.
Ввод - 126, вывод - 2.
Ввод - 127, вывод - 0.

Суть:
У меня не реализован перевод из десятичной системы в двенадцатеричную систему, а он нужен, как я полагаю.
Это значит, что на определенных числах программа сработает неверно.

Можете оценить сам код, может что - то добавить, упростить.
И, может, у Вас есть примеры, как перевести из десятичной в двенадцатеричную систему? Сколько искал, так и не нашел ничего простого. Были универсальные варианты, с применением каких - то огромных (по меркам программы, которую я должен получить) блоков кода...

Заранее спасибо!

P.S.: Не мог использовать цикл for - нельзя, так же нельзя и сторонние библиотеки использовать (math.h, например).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2018, 11:51
Ответы с готовыми решениями:

Найти наименьший натуральный делитель числа
Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель,...

Состоит ли число из одинаковых цифр?
Здраствуйте, помогите пожалуйста написать программу Данно натуральное число N....

Определить состоит ли число из одинаковых цифр
#include&lt;iostream.h&gt; #include&lt;conio.h&gt; #include&lt;math.h&gt; void main() { ...

Найти самый наименьший элемент в матрице, и найти сумму столбца который стоит этот наименьший найденный элемент
Найти самый наименьший элемент в матрице, и найти сумму столбца который стоит...

В представлении десятичного целого числа в n -ой системе счисления (2<=n<=9) найти количество цифр
В представлении десятичного целого числа в n -ой системе счисления (2&lt;=n&lt;=9)...

8
nmcf
6276 / 5578 / 2538
Регистрация: 14.04.2014
Сообщений: 23,468
17.03.2018, 15:01 2
Тогда деление на 12 должно быть.
0
TheTimickRus
0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 20
21.03.2018, 22:00  [ТС] 3
Вот, если, вдруг, кому пригодится =)

Кликните здесь для просмотра всего текста
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include iostream;
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
 
    auto n = 0;
    cout << " Введите число X и нажмите Enter: "; cin >> n;
 
    auto i = 2, div = 0;
    while (i <= n)
    {
        auto f = true;
        
        if (n % i == 0)
        {
            int t1;
            auto t2 = t1 = i;
 
            while (t1 > 0)
            {
                if ((t1 % 12) == t2)
                    t2 = t1 % 12;
                else
                {
                    f = false;
                    break;
                }
 
                t1 /= 12;
            }
 
            if (f)
            {
                div = i;
                break;
            }
        }
        
        i++;
    }
 
    cout << "\n--------------------------\n Ответ: " << div;
 
    cin.get(); cin.get();
    return EXIT_SUCCESS;
}
0
Байт
Эксперт C
18526 / 12031 / 2508
Регистрация: 24.12.2010
Сообщений: 24,302
22.03.2018, 14:07 4
TheTimickRus, Ты ищешь делители, перебирая все числа, а потом проверяешь их на одинаковость цифр.
А я бы пошел другим путем. Ведь чисел c одинаковыми цифрами значительно меньше!
Я бы генерировал именно их и проверял бы - являются ли они делителями.
2
TheTimickRus
0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 20
22.03.2018, 23:22  [ТС] 5
Байт, а ведь да)
Но там же ещё двенадцатеричная система... И вот она меня прям смущает...

Получается, будет что - то такое?:
1) Перебираем все числа от 2 до 9
2) А потом 11, 22, ..., 99, 111, 222, ... 999
0
New man
212 / 140 / 56
Регистрация: 23.05.2011
Сообщений: 740
Завершенные тесты: 4
22.03.2018, 23:30 6
C++
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
29
30
31
// Если возвращает число >X, значит, делителя нет.
unsigned get_divider(const unsigned X, const unsigned digit)
{
   unsigned divider = (digit==1)?(12*1+1):digit;
   while(divider<=X)
   {
      if (x%divider==0)
         return divider;
      divider = divider*12 + digit;
   }
   return divider;
}
 
// В main
unsigned X;
cin>>X;
unsigned divider;
unsigned digit = 1;
 
// Пока не нашли ответ и пока цифры меньше 12
do 
{
   divider = get_divider(X, digit);
   digit++;
}
while(divider>X && digit<12);
 
if (divider>X)
   cout<<"Divider not found\n";
else
   cout<<"Divider is "<<divider<<endl;
С переводом divider в 12-теричную сами разберётесь
1
TheTimickRus
0 / 0 / 0
Регистрация: 30.11.2016
Сообщений: 20
22.03.2018, 23:32  [ТС] 7
New man, спасибо, буду думать ))
0
New man
212 / 140 / 56
Регистрация: 23.05.2011
Сообщений: 740
Завершенные тесты: 4
22.03.2018, 23:52 8
Хотя, у вас проблема как раз с переводом.
Давайте уж напишу.

C++
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
template<unsigned BASE>
std::string get_number_string(const unsigned num);
{
   static_assert(BASE, "Number base must be nonzero");
   if (num==0)
       return "0";
   std::stringstream out_str;
   // Выводим символы в обратном порядке
   while(num)
   {
      const unsigned digit = num%BASE;
      num/=BASE;
      if(digit<10)
         out_str<<digit; // Выводим как есть
      else
         out_str<< ('A'+(digit-10)); // Пользуемся тем, что порядок кодов знаков по алфавиту
   }
   std::string res = out_str.str();
   std::reverse(res.begin(), res.end());
   return res;
}
 
template<>
std::string get_number_string<10>(const unsigned num) {return std::to_string(num);}
 
 
// В main
cout<<get_number_string<12>(divider);
Добавлено через 2 минуты
Ну, и надо заинклудить <string>, <algorithm>, <sstream>

Добавлено через 6 минут
Как вы понимаете, get_number_string — шаблонная функция, которая переводит число в нужную систему счисления (задаётся как BASE).

Она сначала выводит все цифры в обратном порядке в строку, затем переворачивает её, и возвращает.

Вот это отдельная специализация для основания 10 (нет смысла её писать, если это есть в стандартной библиотеке)
C++
1
2
template<>
std::string get_number_string<10>(const unsigned num) {return std::to_string(num);}
И да, по-хорошему, надо ещё сделать отдельную для единицы:
C++
1
2
3
4
5
6
template<>
std::string get_number_string<1>(const unsigned num) {
   std::stringstream out_str;
   for (unsigned i = 0; i<num;++i) out_str<<'1';
   return out_str.str();
}
1
Байт
Эксперт C
18526 / 12031 / 2508
Регистрация: 24.12.2010
Сообщений: 24,302
23.03.2018, 09:51 9
Может быть такой псевдокод будет понятнее
C++
1
2
3
4
5
for(i=1; i<12; i++) {
  for(k=i; k<=N/2; k=12*k + i)
    if (k>1 && N%k==0)  // Этот делитель найден
                                   // Проверить его на минимальность
}
Сейчас вчитался в условие задачи... Наименьший, хмм.. Наименьшим будет 1. Если его исключить, то вполне реальные претенденты - 2, 3, 5, 7, 11(B)... А об их исключении в условии ни слова... Может быть нужен наибольший ? Тогда вот это
Цитата Сообщение от TheTimickRus Посмотреть сообщение
если их нет, вернуть 0).
ни к чему, 1-то всегда есть.
ЗЫ. Да, еще про запрет for. Давно извстно, что любой цикл с for можно записать с помощью while. И наоборот. Или while тоже нельзя? Тогда эта задача не для меня. Я - практикующий программист, а не фокусник, и не очень люблю бегать со связанными ногами...
0
23.03.2018, 09:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.03.2018, 09:51

Найти наименьший общий делитель в произвольном массиве
Товарищи, доброго времени суток! Никак не могу совладать с алгоритмистикой...

Найти все натуральные числа в диапазоне между m и n, в записи которых нет двух одинаковых цифр
Всем привет. Найти все натуральные числа в диапазоне между m и n (m&lt;n), в...

Ввод n-значного числа, вывод цифр, из которых оно состоит и вывод суммы его цифр
Написать программу, осуществляющую ввод n-значного числа, вывод цифр, из...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru