Форум программистов, компьютерный форум CyberForum.ru

Числа-вампиры - C++

Восстановить пароль Регистрация
 
Kaskera
0 / 0 / 0
Регистрация: 27.07.2013
Сообщений: 34
11.08.2013, 14:59     Числа-вампиры #1
Помогите дописать функцию!

Задание со Stanford. Assignment 3: Short Recursion Problems

Искал, нигде не нашел подходящего варианта, который бы работал быстро для чисел с 8 цифр или менее, как того требуют в условии.

Последняя надежда на вас!

http://ru.wikipedia.org/wiki/%D0%A7%...B8%D1%80%D1%8B

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
/**
 * File: vampire-numbers.cpp
 * -------------------------
 * Provides a program that repeatedly prompts the user for positive
 * numbers with an even number of digits and informs them
 * whether the number is a Vampire number or not.
 */
 
#include <string>    // for string
#include <iostream>  // for cout, endl
using namespace std;
 
#include "console.h" 
#include "simpio.h" // for getInteger
#include "strlib.h" // for stringToInteger, integerToString
 
static int getPossibleVampireNumber() {
    while (true) {
        int response = getInteger("Enter a positive integer [or 0 to quit]: ");
        if (response >= 0) return response;
        cout << "Ah, sorry.  I need a nonnegative response.  Try again... " << endl;
    }
}
 
static bool isVampireNumber(int number, int& first, int& second) {
    // replace this line with your own implementation.  You will want
    // to implement this as a wrapper around a second version of isVampireNumber
    // that does the actual recursion.
    return false;
}
 
int main() {
    cout << "Here's a program that tells you whether or not a "
         << "number you enter is Vampire." << endl << endl;
    while (true) {
        int number = getPossibleVampireNumber();
        if (number == 0) break;
        int first, second;
        if (isVampireNumber(number, first, second)) {
            cout << "Woo! " << number << " is a Vampire number, and "
                 << first << " and " << second << " are its fangs." << endl << endl;
        } else {
            cout << "Nope! The number " << number << " isn't Vampire." << endl << endl;
        }
    }
    cout << endl;
    cout << "All done!" << endl;
    return 0;
}
Надо заполнить функцию isVampireNumber. Вот оригинал задания, если кому надо http://www.stanford.edu/class/cs106x...on-Warmups.pdf (Problem 2: Vampire Numbers).

Прикрепил проект со всем нужным, там и демка есть, как оно должно работать.
Вложения
Тип файла: rar Vampire Numbers.rar (534.1 Кб, 5 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.08.2013, 14:59     Числа-вампиры
Посмотрите здесь:

Даны два целых числа A и B (A < B). Вывести в порядке убывания все це-лые числа, расположенные между A и B (не включая числа A и B), а также количеств C++
Дан файл F, компонентами которого являются целые числа. Получить в файле G все нечетные числа, входящие в файл F. Числа в файле G должны следовать C++
C++ От данного числа N вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. до тех пор, пока число положительно
C++ Как написать программу-калькулятор чтобы было можно додавать 2 числа, 3 числа, 4 числа, n чисел?
Даны натуральные числа M, N. Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.08.2013, 17:06     Числа-вампиры #2
простейший перебор без какого-либо усложнения. Единственное, что здесь математически интересно - показать, существует ли решение быстрее, чем перебор. Прошу высказывать все версии.

Добавлено через 9 минут
автор, от вас хотят, чтобы вы написали простой рекурсивный перебор. Попробуйте реализовать его. Вопросы выкладывайте в тему. В принципе, существует решение, которое тут не предполагается, но должно работать. Если оно вам интересно, могу написать.
Kaskera
0 / 0 / 0
Регистрация: 27.07.2013
Сообщений: 34
11.08.2013, 17:12  [ТС]     Числа-вампиры #3
Цитата Сообщение от salam Посмотреть сообщение
простейший перебор без какого-либо усложнения. Единственное, что здесь математически интересно - показать, существует ли решение быстрее, чем перебор. Прошу высказывать все версии.

Добавлено через 9 минут
автор, от вас хотят, чтобы вы написали простой рекурсивный перебор. Попробуйте реализовать его. Вопросы выкладывайте в тему. В принципе, существует решение, которое тут не предполагается, но должно работать. Если оно вам интересно, могу написать.
Напишите, поможет.

Я вот так думал организовать разбор и сбор числа, то есть разбивку на цифры и сборку из цифр.

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
#include <iostream>
 
void toNumber(int data)
{
  while (data !=0 ) {
    std::cout << data % 10; /// вместо cout забираем куда нужно число. например buf = data % 10;
    data /= 10;
  }
}
 
int fromNumber()
{
  int ret = 0;
  int x=1;
  int mas[] = {3, 2, 1};
  for (int i = 0; i < 3; i++) {
    ret += mas[i] * x;
    x *= 10;
  }
  return ret;
}
 
int main()
{
  int mas[3];
  toNumber (123);
  std::cout << " " << fromNumber() << std::endl;
  return 0;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.08.2013, 17:40     Числа-вампиры #4
прошу прощения, я писал первый раз с телефона и не имел возможности посмотреть код... задание, оказывается, только в том, чтобы проверить число на "вампирность"... не хочется изобретать велосипед. я бы просто нашел все делители числа, и проверил, удовлетворяют ли они требованиям.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.08.2013, 18:19     Числа-вампиры #5
Вариант с поиском делителей очень медленный, ведь нужно будет еще проверять вхождение цифр в число, причем каждая цифра должна использоваться один раз.

Вот набросал, все работает. Правда не рекурсия:

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
#include <string>
#include <sstream>
#include <algorithm>
 
bool isVampireNumber( const int num, int &first, int &second ) {
   std::string numStr;
   std::string firstStr;
   std::string secondStr;
   std::stringstream s;
   
   s << num;
   s >> numStr;
   
   int numLength = numStr.length();
   
   if ( numLength & 1 )
      return false;
   
   int partsStr = numLength / 2;
   
   std::sort( numStr.begin(), numStr.end());
   
   do {
      firstStr.assign( numStr.substr( 0, partsStr ));
      secondStr.assign( numStr.substr( partsStr ));
      
      if ( firstStr[ partsStr - 1 ] != '0' || secondStr[ partsStr - 1 ] != '0' ) {
         if (( first = std::atoi( firstStr.c_str())) * ( second = std::atoi( secondStr.c_str())) == num )
            return true;
      }
   } while ( std::next_permutation( numStr.begin(), numStr.end()));
   
   return false;
}
Kaskera
0 / 0 / 0
Регистрация: 27.07.2013
Сообщений: 34
11.08.2013, 18:26  [ТС]     Числа-вампиры #6
Цитата Сообщение от Toshkarik Посмотреть сообщение
Вариант с поиском делителей очень медленный, ведь нужно будет еще проверять вхождение цифр в число, причем каждая цифра должна использоваться один раз.

Вот набросал, все работает. Правда не рекурсия:

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
#include <string>
#include <sstream>
#include <algorithm>
 
bool isVampireNumber( const int num, int &first, int &second ) {
   std::string numStr;
   std::string firstStr;
   std::string secondStr;
   std::stringstream s;
   
   s << num;
   s >> numStr;
   
   int numLength = numStr.length();
   
   if ( numLength & 1 )
      return false;
   
   int partsStr = numLength / 2;
   
   std::sort( numStr.begin(), numStr.end());
   
   do {
      firstStr.assign( numStr.substr( 0, partsStr ));
      secondStr.assign( numStr.substr( partsStr ));
      
      if ( firstStr[ partsStr - 1 ] != '0' || secondStr[ partsStr - 1 ] != '0' ) {
         if (( first = std::atoi( firstStr.c_str())) * ( second = std::atoi( secondStr.c_str())) == num )
            return true;
      }
   } while ( std::next_permutation( numStr.begin(), numStr.end()));
   
   return false;
}
Спасибо! Я проанализирую код, мне поможет.

А как рекурсивно реализовать? От меня ведь этого требуют.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
11.08.2013, 19:16     Числа-вампиры #7
Цитата Сообщение от Toshkarik Посмотреть сообщение
Вариант с поиском делителей очень медленный
попробуйте проанализировать вопрос, прежде чем людям мозг...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.08.2013, 19:31     Числа-вампиры
Еще ссылки по теме:

C++ Поменять одну из цифр первого числа с цифрой второго числа, чтобы получившиеся числа были взаимно простыми
Даны два числа. Если квадратный корень из второго числа меньше первого числа, то увличить второе число в пять раз с++ C++
Ввести в программу строку (числа, латиница), считать только числа, записать числа в массив C++

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

Или воспользуйтесь поиском по форуму:
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
11.08.2013, 19:31     Числа-вампиры #8
salam, не понял, Вы к чему это вообще? О каком вопросе и о чьем мозге идет речь?
Yandex
Объявления
11.08.2013, 19:31     Числа-вампиры
Ответ Создать тему
Опции темы

Текущее время: 06:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru