Найти самый большой палиндром от произведения двух N-значных чисел


Программа находит самый большой палиндром, изготовленные из произведения двух П-разрядных чисел, где N не задан пользователем.

В код включены произведения, однако, когда пользователь вводит 5 или более, программа работает очень медленно. Я считаю, что это \$o(п^2)\$ (не стесняйтесь, чтобы исправить оценки необходимости).

Хотелось бы отзывы/Отзывы о каких-либо "лучших практик" я должен следовать, наряду с производительностью и читабельностью.

Класс:

#include <math.h>

class FindPalindrome {

    private:

        //multiplicand 1
        int number_one; 
        //multiplicand 2
        int number_two;
        //holds current product
        int current;
        //copy of current product copy so as the current var values is not manipulated as its original will be needed
        int copy;   
        //holds most recently discovered palindrome
        int palindrome; 
        //holds greatest palindrome discovered 
        int greatest;
        //as determined by number of digits for operand
        int upper_limit; 
        int lower_limit;

    public:

        //Constructor
        FindPalindrome(int digits_requiered);

        //Accessors
        int Greatest_Palindrome_Found();

        //Mutators
        void Product_Generator();
        void Determine_if_Palindrome();  
};


FindPalindrome::FindPalindrome(int digits_requiered){

    upper_limit = pow(10, digits_requiered) - 1;
    lower_limit = pow(10, digits_requiered -1);

    number_two = number_one = upper_limit;

     current = 0;
     copy = 0;  
     palindrome = 0;
     greatest = 0;

}


int FindPalindrome::Greatest_Palindrome_Found(){

    return greatest;
}


void FindPalindrome::Product_Generator(){

    while (number_one >= lower_limit) {
        number_two = upper_limit;
        while (number_two >= lower_limit) {
            if(number_one >= number_two)
            {   
                //test initial numbers to see if they generate palindrome
                Determine_if_Palindrome();
            }
            number_two = number_two - 1;            
        }
        number_one = number_one - 1;
    }
}


void FindPalindrome:: Determine_if_Palindrome(){

    //used in determining length of array and storing product into array
    int array_length = 0;
    //copy of array length so that original length value is still available
    int array_length_cpy = 0;   
    //vars for checking for palindrome properties
    int head = 0;
    int tail = 0;
    int retrieve_one = 0;
    int retrieve_two = 0;

    current = number_one * number_two;
    copy = current;

    //get length of number and create array to hold number
    while (copy != 0) {
        copy /= 10;
        ++array_length;
    }

    int store[array_length];

    //restore to products value for extraction manipulations
    copy = current;

    array_length_cpy = array_length;
    //extract digits from number and poopulate array
    for (int i = array_length_cpy; i>0; --i) {
        store[i-1] = copy%10;
        copy/=10;
        --array_length_cpy;
    }

    //Compare last and first digits then move "inwards" comparing the digits
    tail = array_length -1;

    retrieve_one = store[head];
    retrieve_two = store[tail];

    if (retrieve_one == retrieve_two) {
        for (int i = (array_length/2); i > 0; --i) {
            tail = tail -1;
            head = head + 1;
            retrieve_one = store[head];
            retrieve_two = store[tail];

            if (retrieve_one != retrieve_two) {
                return;
            }
        }

        palindrome = current; //it is a palindrome

        //test for if it is the biggest one found yet
        if (current > greatest) {
            greatest = current;

        }
    }     
}

главная()

#include <sys/time.h>
#include <iostream>
#include "FindPalindrome.h"

using namespace std;


int main () { 

    int digits_specified = 0;

    cout << "Please enter the number of digits: ";
    cin>>digits_specified;
    cout << "\n";

    //For testing purposes to print out all palindromes generated
    /*
    std::cout << "Operand 1" <<"\t\t";
    std::cout << "Operand 2" <<"\t\t";
    std::cout << "Product" <<"\t\t\n\n";
    */

    FindPalindrome trial1(digits_specified);

    //find palindrome and record the time it took to do this
    struct timeval start, end;
        long mtime, seconds, useconds;

        gettimeofday(&start, NULL);
        //start actual calculation for palindrome
    trial1.Product_Generator();
    gettimeofday(&end, NULL);

    seconds  = end.tv_sec  - start.tv_sec;
        useconds = end.tv_usec - start.tv_usec;
        mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;
    cout << "\n";
        printf("Elapsed time: %ld milliseconds\n", mtime);
    cout << "\n";
    cout<<endl<< "Largest palimdromic number: "<< trial1.Greatest_Palindrome_Found()<<endl; 
    cout << "\n";
        return 0;
}


4071
6
задан 8 июля 2011 в 06:07 Источник Поделиться
Комментарии
2 ответа

Во-первых, в качестве общего замечания, которые вы сделали, созданные по сути все ваши переменные, как принадлежность к FindPalindrome объекта. ИМО, это ошибка. Каждая переменная должна иметь минимальный объем необходимой для выполнения работы. Любая переменная, которая используется только внутри определенной функции, например, должны быть локальными для этой функции, а не класса. Переменная, которая используется только в определенный цикл должен быть локальным, что петля и т. д.

После этого, я хотел взглянуть на DetermineIfPalindrome. Во-первых, я бы изменить его на что-то вроде:

bool is_palindrome(int number);

Она должна быть просто чистой функции, что указывает на его вход является палиндромом или нет. Затем вы используете это, чтобы решить, что (если ничего), чтобы сделать с определенным номером.

Как это реализовано, я бы для начала отметив, что длина товара (в большинстве) сумма длин входов (например, продукт 2 5-значных чисел будет не более 10 цифр). Это означает, что вы можете предварительно выделить место для преобразованного числа вместо того, чтобы делать большую часть работы для перевода, чтобы подобрать размер, то распределение пространства, а затем выполнить преобразование. Это должно примерно вдвое быстрее, что часть кода.

Глядя на следующий шаг, Product_Generator использует цикл while, где кажется, что для петли будет иметь больше смысла. Это также, кажется, генерировать (и игнорирует) некоторые цифры, которые вы, видимо, не волнует. Похоже, что это должно быть что-то вроде этого:

int Product_Generator() { 
int greatest = 0;
for (int i=upper; i>=lower; --i)
for (int j=upper; j>=i; --j) {
int product = i * j;
if (product > largest && is_palindromic(product))
greatest = product;
}
return greatest;
}

Глядя на общий дизайн класс, я хотел отметить две вещи: во-первых, вы сделали практически все общественные, где все (или почти все) будет частная. Во-вторых, его имя означает действие (глагол), которое указывает, что он, вероятно, должен вести себя как функция. В конечном счете, она принимает входные данные (количество цифр) и создает один выходной (нужные палиндром).

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

class FindPalindrome { 
int lower, upper;

bool is_palindrome(int);
public:
FindPalindrome(int digits) :
lower(pow(10, digits_required -1)),
upper(pow(10, digits_required)-1))
{}

int operator()() {
// This is a renamed version of what's shown above as Product_Generator
}
};

Другая вещь, чтобы рассмотреть будет, стоит ли идти на это в другом направлении -- начнем с создания палиндромов, и коэффициент каждого палиндрома, чтобы увидеть, если мы можем найти факторы, правильное количество цифр. Разложение больших чисел становится довольно медленным, но, как факторинг выходит, мы имеем дело с достаточно малыми числами здесь (для факторинга, "большие" обычно означает что-то вроде 100 цифр и более). Я не уверен, что закончилось бы быстрее, но это может. Это тоже было бы довольно легко для создания палиндромов в строго убывающем порядке, поэтому первое, что мы нашли с факторами правильного размера будет окончательный ответ.

11
ответ дан 8 июля 2011 в 10:07 Источник Поделиться

1) гид по стилю

Я хотел бы начать с несколько типс стиль. Возьми это с большим недоверием, так как это субъективно.

1) функции C++, как правило, строчные в то время как классы являются прописными.

2) члены класса C++, как правило, есть какие-то особые идентификаторы, такие как знак нижнего подчеркивания или приставкой "бы".

Это не его стиль руководства, давайте поговорим дизайна класса :)

2) нахождение палиндрома

Вы назвали свой FindPalindrome класса, что хорошо, но немного сбивает с толку. Мне нравится название классов после их поведения, например, PalindromeFinder. Также, вы использовали FindPalindrome в единственном числе, но вы хотите ограничить каждого экземпляра только один палиндром? Ваш дизайн предполагает не.

Во-вторых, вы не используете STL в вашу пользу. Давайте подумаем о природе палиндромы немного. Кроме строк, палиндром-это любое число, которое можно прочитать одинаково спереди назад, например

обратный(10011001) = 10011001.

Ваша функция determine_palindrome, кажется, предполагают, что вы нарушаете массива в цифры, а затем сравнивать их по одному. Отлично, ты на правильном пути; сейчас пусть стл помочь вам.

std::vector<int> digits  = Utility::toArray<int>(number);
std::vector<int> reverse = digits;
std::reverse(reverse.begin(), reverse.end());

Вместо массива, я использовал вектор, поэтому мне не нужно обременять себя с графом массива или уродливые функции, которые заботятся о том, что для меня. Она также имеет копию-конструктор, который позволяет мне определить второй массив с точно такими же цифрами, как и первый. Третья строка меняет эту последовательность цифр.

Теперь все, что осталось сделать, это проверить, если обратное и цифры такие же цифры для цифры:

for (int i(0); i < digits.size(); ++i)
if (digits[i] != reverse[i])
return false;
return true;

Это мой весь боол isPalindrome(число int) функция. Больше ничего не надо, я просто должен был использовать STL в мою пользу. Если вы еще не читали на заголовок все же я настоятельно рекомендую вам сделать :)

Что касается производительности, то эта функция выполняется за o(n) в (линейное) время.

3) обязанности

Это принцип ООП. Всегда стараюсь дать каждой и функции класса ровно одна ответственность.

Вы видели функцию полезности::метод toArray(количество) в моем разделе на нахождение палиндрома? Вы имели это внутри вашей функции. Мой вопрос к вам: это отвечает функция, которая определяет, является ли число палиндромом, чтобы также разбить число на цифры?

Ответа нет. В isPalindrome функции находит палиндром, вот и все. Вы можете выполнить рефакторинг кода, которая разбивает число на цифры в его собственную функцию, как у меня. Templatize его и там вы идете, вы можете использовать его для целого ряда других чисел (ну, целых чисел...).

4) с const-корректность

Это большой один. Все константы, может быть const. Почему? Безопасности. Почему еще? Другие программисты могут рассчитывать на гарантии, которые дает функции, которые они называют.

Простое правило как const-корректность: если функция не изменяя никаких аргументов, сделать это const. Ваша функция greatest_palindrome только возвращает наибольший палиндром, и ничего другого. Сделать это const.

Как Джерри указал все необходимые переменные были объявлены в самом классе, а не функции. Если вам изменили, вы могли бы сделать некоторые другие константные функции, а также. Всегда стремиться к этому!

5) знать свои функции

Посмотрите на перегрузки для военнопленных (с cplusplus.com):

double pow (      double base,      double exponent );
long double pow ( long double base, long double exponent );
float pow ( float base, float exponent );
double pow ( double base, int exponent );
long double pow ( long double base, int exponent );

Все они используют дублеров и возврата удваивается. Парный медленный, вы работаете только с целыми значениями. Выполните умножение себя. Это также относится к библиотека. Посмотрите вокруг! Ценный материал.


Я думаю, что это зашло слишком далеко. Наряду с предложениями от Джерри, ваш код должен работать быстрее. Вот моя реализация (без функции для верхнего и нижнего пределов. Вместо этого он просто берет цифры из командной строки.).

#include <vector>
#include <algorithm>

namespace Utility
{
// See boost::noncopyable for details.
class Uncopyable
{
protected:
Uncopyable() {}
virtual ~Uncopyable() {}

private:
Uncopyable(Uncopyable const&);
Uncopyable& operator=(Uncopyable const&);
};

// We can apply template specialization to handle more than just integral data types.
template <typename T>
std::vector<T> toArray(T num)
{
std::vector<T> ret;

while (num)
{
ret.push_back(num % 10);
num /= 10;
}

return ret;
}
}

// Alternate to Uncopyable is boost::noncopyable.
class PalindromeFinder : public Utility::Uncopyable
{
public:
PalindromeFinder();

void feed(int number);

int greatestPalindrome() const;

void operator()(int number);

private:
bool isPalindrome(int number) const;

private:
int greatestPalindrome_;
};

// Make sure our members are not in an undefined state.
PalindromeFinder::PalindromeFinder()
: greatestPalindrome_(0)
{ }

// Replace me with your upper- and lower-limit implementation :3
void PalindromeFinder::feed(int number)
{
if (isPalindrome(number) && number > greatestPalindrome_)
greatestPalindrome_ = number;
}

bool PalindromeFinder::isPalindrome(int number) const
{
std::vector<int> digits = Utility::toArray<int>(number);
std::vector<int> reverse = digits;
std::reverse(reverse.begin(), reverse.end());

// We could optimize this further by only going through half the vector's elements.
for (int i(0); i < digits.size(); ++i)
if (digits[i] != reverse[i])
return false;

return true;
}

// No numbers fed? Then our palindrome is 0.
int PalindromeFinder::greatestPalindrome() const
{
return greatestPalindrome_;
}

void PalindromeFinder::operator()(int number)
{
feed(number);
}

6
ответ дан 13 июля 2011 в 04:07 Источник Поделиться