VPF::[Java] Палиндромы - Форум программистов

SERJ2006

Дата 24.1.2012, 19:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

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

Условие: Получить все меньшие 10^6 натуральные числа, которые являются палиндромами (его запись читается одинаково с начала и с конца) как в десятичной, так и в двоичной системах.

Текс программы:

Код


public class Palindrom2{
public void main (){
String s, sp, b2;
for(int i=0; i<1000000; i++){
s=""+i;}
}
public String ObratChis(String s){
String s1="";
for(int i=s.length()-1; i>=0; i--){
char c=s.charAt(i);
s1+=c;}
return s1;}
public void sravnenie(){
String  s,s1;
if (s.equals(s1)==true) 
 {String b1=java.lang.String.toBinaryString(s); //проблема в этой строке выдает ошибку"cannot find symbol - method toBinaryString(java.lang.string)
return b1;}
if(s.equals(s1)==false) System.out.println("Не палидром!!!");
 
System.out.println(b1);
System.out.println(s);}
}

Мне нужно чтобы она выводила все числа в этом диапазоне палиндромы в двоичной и десятичной системах счисления. Но она не доделана, я запутался. Помогите доделать пожалуйста и исправить. Спасибо за внимание.

jk1

Дата 24.1.2012, 20:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

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

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

--------------------

Opinions are like assholes — everybody has one

Mirkes

Дата 25.1.2012, 13:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 4
Всего: 17

Метод toBinaryString принадлежит объекту Integer.

--------------------

Mirkes

Дата 26.1.2012, 13:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 4
Всего: 17

Мне понравилась задачка и я ее решил.

Код


public class Palindrom {
    private static int maxN = 2;
    public static void main(String args[]) {
        // Первая идея - не перебирать все числа, а срагу генерировать только палиндромы
        // в десятичной системе счисления. Среди них отбирать палиндромы в двоичной системе
        // счисления.
        // В условиях задачи сказано, что число менее миллиона, то есть оно содержит от 1 до
        // пяти знаков. Используем это условие явно.
        // Среди палиндромов можно выделить два типа - с четным числом знаков и с нечетным.
        // Палиндромы с четным числом знаков имеют вид a1a2...anan...a2a1
        // Палиндромы с нечетным числм знаков имеют вид a1a2...anan+1an...a2a1
        // Легко заметить, что каждому палиндрому с четным числом цифр соответвует
        // 10 палиндромов с нечетным числом цифр.
        // Так же легко заметить, что а1!=0.
        // Создадим рекурсивную процедуру порождения палиндромов с ограничением на n. generPal10.
        // Параметры - уже порожденная глубина m, число, соответсвующее начальной части палиндрома
        // b и число соответсвующее конечной части палиндрома e, dm=10^m
        generPal10(0,0,0,1);
    }

    public static void generPal10(int m, int b, int e, int dm) {
        // Сначала породим нечетные палиндромы с ранее сгенерированными цифрами
        // Поскольку мы собираемся вставлять цифру, то начальное число нужно умножить
        // на 10
        b*=10;
        int p; // число для сбора палиндрома
        String s1, s2;
        for (int i = 0; i < 10; i++) {
            p = b + i * dm + e;
            s1 = Integer.toBinaryString(p);
            s2 = ObratChis(s1);
            if (s1.equals(s2)) {
                System.out.println(""+p+"   "+s1);
            }
        }
        // Не пора ли кончать?
        if (m==maxN){
            return;
        }
        // теперь палиндромы с четным числом цифр, но с большим.
        // a1!=0
        int j=0;
        if (m==0){
            j=1;
        }
        int dm1=10*dm; // константа для следующего уровня
        b*=10; // Для четных начало следует умножить еще раз на 10.
        m++;
        for (int i=j;i<10;i++){
            // Сначала отработаем полученныйй палиндром
            p=b+(dm1+dm)*i+e;
            s1 = Integer.toBinaryString(p);
            s2 = ObratChis(s1);
            if (s1.equals(s2)) {
                System.out.println(""+p+"   "+s1);
            }
            // Потом вызовем генерацию следующего уровня
            generPal10(m,b+dm1*i,e+dm*i,dm1);
        }
    }

    public static String ObratChis(String s) {
        String s1 = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            s1 += c;
        }
        return s1;
    }
}

Можно увеличивать разрядность. Все равно таких дваждв палиндромов мало.

--------------------

Mirkes

SERJ2006

Дата 26.1.2012, 14:49 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

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

а я все- таки поступил так:

Код


public class Palindrom {
        public static void main(String[] args) {//метод main
            System.out.println ("+++++++++++++++++++++++++++++++++++++");
            System.out.println ("++++++++++++++Задача 2.7++++++++++++++");
            System.out.println ("++++++++++++++++++++++++++++++++++++++");
            System.out.println (" \tПалиндром");
             System.out.println ("Деситичная система \t Двоичная система");//вывод 
                  for (int i = 1; i <1000000; i++) {//цикл проверки на палиндромность от 1 до 1000000
                        if (Palindrom(i) && Binary(i))//есди число палиндром в десятичной и двоичной системе
                                System.out.println("Десятичная запись: " + i + " \tДвоичная запись " + Integer.toBinaryString(i));//то выводить его в десятичной и двоичной системе
                }
        }
 
        public static boolean Palindrom(int i) {//метод проверки на полиндромность в десятичной системе счисления
                String a = String.valueOf(i);//перевод числа i в строку a
                  StringBuffer b = new StringBuffer(a);//создание строки b типа StringBuffer
                  StringBuffer m = b.reverse();//перевернутая строка b
                 boolean d = a.equals(m.toString());//сравнение строк a и m, и занесение в переменную d значение true, если палиндром; false в случае, если он не палиндром
                 return d;//возвращает переменную d  булевского типа
        }
 
        public static boolean Binary(int i) {//метод вывода числа в двоичной записи
                String a=java.lang.Integer.toBinaryString(i);//запись числа i в двоичной системе счисления в тип String
                 StringBuffer b = new StringBuffer(a);  //создание строки  типа StringBuffer
                 StringBuffer m = b.reverse();//перевернутая строка u
                boolean f = a.equals(m.toString());  //сравнение строк f и bin, и занесение в переменную f значение true, если палиндром; false в случае, если он не палиндром
                return f;//возвращает переменную f  булевского типа
                  }
}

Mirkes

Дата 26.1.2012, 18:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: 4
Всего: 17

Согласен. Ваше решение хорошо тем, что дает числа в порядке возрастания.
Однако, многократная проверка чисел, которые заведомо не могут быть палиндромами является излишней тратой времени.
Если сравнить наши методы по скорости, то Ваш окажется существенно более медленным.
Я запустил свой на числах от 0 до 1.000.000.000 - работал около 1с
Ваш снял после полутора минут. Проверялись еще восьмизначные числа. То есть по грубой оценке - порядка 20 минут.
Еще одна ошибка в моем алгоритме - я вывел ноль. Не стоило, посколку он не натуральное число. Я не внимательно прочитал условие.
Эта ошибка легко устраняется. А вот получить числа в порядке возрастания моим алгоритмом нельзя. Разве что потом сортировать.

--------------------

Mirkes

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »