Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Числа-палиндромы, Как оптимизировать? 
:(
    Опции темы
admin82
Дата 30.8.2006, 09:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
Снова добрый!
Надо найти все числа-палиндромы меньшие N, которые при возведении в квадрат тоже дают палиндром. 
Вот моя наработка (функцию pal подсмотрел)
Код

#include "stdafx.h"
#include "iostream"
#include "string.h"
#include "math.h"
using namespace std; 
int pal(char s[100]);

int _tmain(int argc, _TCHAR* argv[])
{
    long number,t;
    char N[100], M[100];
    cout<<"Vvedite N: ";
    cin>>number;
    for (long i = 1; i<=number; i++)
    {
        t = (pow(double(i),2));
        itoa(t,M,10);        
        itoa(i,N,10);        
        if ((pal(N))&&(pal(M))) 
        cout<<i<<endl;
    }
    return 0;
}

int pal(char s[100])
{ 
    int l;
    char s1[100];
    if (strlen(s)<=1)
        return 1;
    else 
    {
        l=s[0]==s[strlen(s)-1];
        strncpy(s1, s+1, strlen(s)-2);
        s1[strlen(s)-2]='\0';
        return l&&pal(s1);
    }
}


По-моему, слишком нерационально. И еще, может, дадите ссылочку на вопросы преобразования чисел в строку и наоборот. VS 2005 сильно ругается на atoi и itoa. А что у него есть взамен?
PM MAIL   Вверх
Sceptik
Дата 30.8.2006, 09:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 36
Регистрация: 29.8.2006
Где: Екатеринбург

Репутация: нет
Всего: нет
admin82, хм.. зачем тебе массивы по 100 байт. тебе с лихвой хватит 11.

для возведение в ЦЕЛУЮ степень никогда не используй pow. К тому же тебе надо возводить в квадрат. Проще и быстрее просто l * l.

Это сообщение отредактировал(а) Sceptik - 30.8.2006, 09:26
PM MAIL ICQ   Вверх
Mayk
Дата 30.8.2006, 09:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


^аВаТаР^ сообщение>>
****


Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134
Вопрос на засыпку - 10 это палиндром?
ЗЫ. 10 * 10 = 010 * 010 = 00100

Это сообщение отредактировал(а) Mayk - 30.8.2006, 09:29


--------------------
 Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.
PM MAIL WWW ICQ   Вверх
admin82
Дата 30.8.2006, 09:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
По поводу степени - исправил, спасибо. А для степени, скажем, 7, что использовать? Или если степень известна только по ходу выполнения программы? 

А вопрос про десятку не понятен. Кто сказал, что натуральные числа мы можем записывать в такой форме для исследования на палиндромность. 10 не будет являться палиндромом, и программа так и решает.
PM MAIL   Вверх
Sceptik
Дата 30.8.2006, 09:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 36
Регистрация: 29.8.2006
Где: Екатеринбург

Репутация: нет
Всего: нет
admin82, 

Код

#include <boost/lexical_cast.hpp>

bool ispalindrom(long int number)
{
    std::string sNumber = boost::lexical_cast<std::string>(number);

    if (sNumber.length() < 2 || (sNumber.length() % 2) != 0)
        return false;

    int half = sNumber.length() / 2;

    if (std::string(sNumber.begin(), sNumber.begin() + half) != std::string(sNumber.begin() + half, sNumber.end()))
        return false;

    return true;
}
PM MAIL ICQ   Вверх
admin82
Дата 30.8.2006, 09:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
Sceptik,
с таким текстом не разберусь. Может, получиться немного (а вернее, много) комментариев? 
Код

#include <boost/lexical_cast.hpp>     
  это что? 
Вместо std::string можно включить include "string.h"? 

boost::lexical_cast<std::string>(number);  -- поясни, пжл.

if (std::string(sNumber.begin(), sNumber.begin() + half) != std::string(sNumber.begin() + half, sNumber.end())) 
то же тамое.

У меня в багаже столько информации нету. 
PM MAIL   Вверх
likehood
Дата 30.8.2006, 10:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


666
**


Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24

Код

bool ispal(long n)
{
    long p = 0, n1 = n;
    do {
        p *= 10;
        p += n1%10;
        n1 /= 10;
    } while (n1 != 0);
    return p == n;
}


А возводить в целую степень можно просто умножая в цикле число само на себя.
PM MAIL   Вверх
admin82
Дата 30.8.2006, 10:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
Теперь есть такой текст:
Код

#include "stdafx.h"
#include "iostream"
#include "string.h"
#include "conio.h"
using namespace std; 
bool ispal(long n);

int _tmain(int argc, _TCHAR* argv[])
{
    long number,t;
    cout<<"Vvedite N: ";
    cin>>number;
    for (long i = 1; i<=number; i++)
    {
        t = i*i;
        if (ispal(t)&&ispal(i))
        cout<<i<<endl;
    }
    getch();
    return 0;
}


bool ispal(long n)
{
    long p = 0, n1 = n;
    do {
        p *= 10;
        p += n1%10;
        n1 /= 10;
    } while (n1 != 0);
    return p == n;
}


Но нельзя ли все же не перебирать все числа до N?

И остается вопрос к Sceptik. Интересно, что он там такое использовал.

Добавлено @ 10:19 
Попробуйте запустить. Введите n = 9999999. Перед выводом последних трех чисел есть СУЩЕСТВЕННАЯ задержка. 
PM MAIL   Вверх
likehood
Дата 30.8.2006, 10:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


666
**


Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24
Цитата(admin82 @  30.8.2006,  11:15 Найти цитируемый пост)
Но нельзя ли все же не перебирать все числа до N?

Похоже что нельзя.
Вдруг N само окажется таким числом.

Это сообщение отредактировал(а) baronp - 30.8.2006, 10:22
PM MAIL   Вверх
likehood
Дата 30.8.2006, 10:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


666
**


Профиль
Группа: Участник
Сообщений: 536
Регистрация: 21.12.2005

Репутация: 8
Всего: 24
Цитата(admin82 @  30.8.2006,  11:15 Найти цитируемый пост)
Введите n = 9999999

У меня весь цикл занял всего 13 сек.
Кстати, вместо long лучше использовать unsigned __int64.
PM MAIL   Вверх
MAKCim
Дата 30.8.2006, 10:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Воін дZэна
****


Профиль
Группа: Экс. модератор
Сообщений: 5644
Регистрация: 10.12.2005
Где: Менск, РБ

Репутация: 52
Всего: 207
Цитата

Код

 t = i*i;


возможен выход за разрядную сетку


--------------------
Ах, у елі, ах, у ёлкі, ах, у елі злыя волкі ©
PM MAIL   Вверх
admin82
Дата 30.8.2006, 11:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
Цитата

У меня весь цикл занял всего 13 сек.

Так разве это мало?????

Цитата

возможен выход за разрядную сетку

Как с этим бороться

Цитата

Кстати, вместо long лучше использовать unsigned __int64.

Поправил, на всякий
PM MAIL   Вверх
Sceptik
Дата 30.8.2006, 11:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 36
Регистрация: 29.8.2006
Где: Екатеринбург

Репутация: нет
Всего: нет
Код

bool ispalindrom(long int number)
{
    // 
    //    boost::lexical_cast - в данном случае преобразует число в строку.
    //                        http://www.boost.org
    std::string sNumber = boost::lexical_cast<std::string>(number);

    // Если число однозначное(один знак :) ) или число знаков нечетно,
    // тогда оно точно не четное.
    if (sNumber.length() < 2 || (sNumber.length() % 2) != 0)
        return false;

    // Вычисляем половину длины числа
    int half = sNumber.length() / 2;

    // Тааак... Теперь самое сложно для новичков..
    // std::string - те кто не знаком это шаблоный класс строк в С++.
    // Все Папки и Гуру С++ рекомендуют(!!!!!!!) пользоваться STL
    // мы так и поступим..
    // в этой строке создаеться две времнных строки
    // и инициализируються итерараторами (мда.. тепреь придеться рассказыать что такое итератор.. эх)
    // В реализации std::string (ну по крайне мере не дебажной) итератор представляет собой прсотой указатель
    // в нашем случае char *. Т.е. если у нас есть например число 123456
    // sNumber.begin(), sNumber.begin() + half == "123" а sNumber.begin() + half, sNumber.end() == "456"
    // после этого мы просто сравниваем две строки.. (благо определен оператор == )
    // если строки не равны.. значит число не полеанд.
    if (std::string(sNumber.begin(), sNumber.begin() + half) != std::string(sNumber.begin() + half, sNumber.end()))
        return false;

    return true;
}


Спасибо за внимание.
P.S. boost::lexical_cast впринципе можно заменить на манипуляцию с snprintf
PM MAIL ICQ   Вверх
Vyacheslav
Дата 30.8.2006, 11:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 2124
Регистрация: 25.3.2002
Где: Москва

Репутация: 9
Всего: 59
Sceptik, 
Палиндром -это не когда левая часть равна правой, а когда  запись  числа прочитанное, слева на право дает число равное числу, полученному при чтении справа налево
121 - это тоже палиндром. Формально все числа от 0 до 9 - тоже палиндромы
Тогда уж
Код

#include <string>
#include <stdio.h >
using namespace std;
 bool ispalindrom(long int number)
{
    char buf[100];
    sprintf(buf, "%d",number);
    string sNumber(buf); ;
    return sNumber == string(sNumber.rbegin(), sNumber.rend());
 }  




--------------------
С уважением, Вячеслав Ермолаев
PM MAIL WWW ICQ   Вверх
Sceptik
Дата 30.8.2006, 12:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 36
Регистрация: 29.8.2006
Где: Екатеринбург

Репутация: нет
Всего: нет
Vyacheslav,  да да.. я немного ошибся.

Это сообщение отредактировал(а) Sceptik - 30.8.2006, 12:03
PM MAIL ICQ   Вверх
admin82
Дата 30.8.2006, 15:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 73
Регистрация: 22.8.2006

Репутация: нет
Всего: 1
Всем спасибо. Остановился на варианте 
Код

bool ispal(unsigned __int64 n)
{
    unsigned __int64 p = 0, n1 = n;
    do {
        p *= 10;
        p += n1%10;
        n1 /= 10;
    } while (n1 != 0);
    return p == n;
}
PM MAIL   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0895 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.