Функция числового палиндрома не возвращает наибольший палиндром
Я пытаюсь создать функцию, которая находит самый большой палиндром, состоящий из трехзначных множителей . Когда я запускаю код, он находит палиндром, но он не самый большой. Не критикуйте мой код, особенно переход, так как я новичок в C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int isPalindrome(int number) {
int palindrome = 1;
char *str = (char *)malloc(8 * sizeof(char));
sprintf(str, "%d", number);
int len = strlen(str);
for (int i = 0; i < len; i++) {
if ((str[i] == str[len - (i+1)]) && palindrome) continue;
else palindrome = 0;
}
free(str);
return palindrome;
}
int main(void) {
char* omg = "\xF0\x9F\x98\xB2";
int factorI = 0;
int factorJ = 0;
for (int i = 999; i >= 100; i--) {
for (int j = 999; j >= 100; j--) {
if (isPalindrome(i * j)) {
factorI = i;
factorJ = j;
goto end_loop;
}
}
}
end_loop: printf("Done! Found palindrome. (%s%s%s)\n", omg, omg, omg);
printf("i: %d\nj: %d\n", factorI, factorJ);
printf("PALINDROME: %d", factorI * factorJ);
printf("\n\nHello World\n");
return 0;
}
Когда я запускаю код, я получаю это:
Done! Found palindrome. (😲😲😲)
i: 995
j: 583
PALINDROME: 580085
Hello World
Но, похоже, это не самый большой палиндром, потому что, когда я ввожу его в Проект Эйлера , он помечает решение как неверное. Может ли кто-нибудь помочь отладить мой код и посмотреть, где я напортачил? Я просмотрел его раза три и ничего не нашел. ПОЖАЛУЙСТА, не указывайте мне правильные коэффициенты/палиндром, просто помогите мне с моим кодом.
Ну, я не вижу кода, сравнивающего палиндромы, который экономит максимум? Другие заметки, "%d" в sprintf(), могут содержать 12 символов, требующих хранения не менее 13 байтов для хранения в виде строки. Просто используйте char str[32] и избегайте malloc(), он не нужен (правило: никогда не экономьте на размере буфера...). Кроме того, если вы используете mailloc(), это char *str = malloc (nbytes); Вам не нужно sizeof(char), это 1. и посмотрите Приведу ли я результат malloc? И... использование goto совершенно нормально — это единственный командный способ разорвать вложенные циклы в C :)
Посмотрите на свой основной вложенный цикл. Как только он находит самый первый палиндром, он сразу же переходит к end_loop и печатает его. Это не поиск самого большого палиндрома. Он находит первого попавшегося.
Вы можете подумать, что обратный цикл гарантирует, что вы найдете наибольшее число. Это не так. Рассмотрим простой случай зацикливания i и j вниз от 3 до 1. Ваш цикл выглядит как 9,6,3,6,4,2,3,2,1. Если действительны и 3, и 4, вы найдете 3 вместо 4.
Кроме того, вам не нужно зацикливать i < len, достаточно i < len/2, поскольку вы сравниваете байты с каждого конца и работаете к середине. Другой способ — просто установить i = 0 и j = len - 1, а затем зациклить while (i < j) { /* do stuff */; i++, j--; }.
«Не критикуйте мой код [..], поскольку я новичок в C» — это довольно странное мнение, поскольку вы новичок, разве вы не хотите научиться становиться лучше?
Указывает ли Project Euler смайлики как часть ответа?
@GuyIncognito — Я думаю, что они хотели бы помощи, но не хотели бы, чтобы их оскорбляли. В идеале именно так и следует решать каждый вопрос. Согласитесь с Н.М., если только вам не нужны смайлы, они на самом деле не нужны и в любом случае не переносятся между терминалами. Большинство увидит просто квадратные рамки.
@ Крис, ну, я не спрашиваю о моей функции палиндрома. Идеально. Извините за формулировку, я сделал это вчера вечером в 22:00.
@Дэвид Мне нравится sizeof(char) для удовольствия глаз, потому что он показывает, что я не просто набираю случайные числа. Поэтому, когда я делаю sizeof(int), он всегда возвращает 4, но вы знаете, сколько байтов займет ваше int.
@OnyxWingman на разных платформах sizeof(int) не всегда возвращает 4.
@TomKarzes Я не уверен, где я ошибся, но теперь, когда я смотрю на это ... ни один палиндром с трехзначными коэффициентами не может использовать коэффициент больше 995, но что, если мы используем палиндром меньше 995 с одним больше 583, что даст палиндром большего размера? Если бы мне пришлось полностью пройти через I и J, это заняло бы 800 000 раз, и это наверняка заставит мою программу работать вечно, и я не хочу ждать час, пока мой код полностью пройдет через I и J. Есть ли способ сделать это быстрее?
@Крис, но sizeof(char) всегда возвращает четыре?
sizeof(char) всегда возвращается 1.
@WeijunZhou ах, кажется, теперь я понял! Спасибо!
@n.m.couldbeanAI Действительно, я просто пишу код, чтобы получить ответ. Проект Эйлер принимает число, но я не хочу обманывать и спрашивать ИИ... Я хочу сделать это так, как они это делали раньше, с помощью C.
Суть в том, что int не обязательно должен быть 4-байтовым по стандарту C, он может быть 2 и т. д. Существуют некоторые реализации-единороги, древнее оборудование и т. д., которые не используют 4 байта для int . В нынешнем мире, типа единорога, я не встречал, но есть такие, которые клянутся, что они существуют. Раньше они были довольно частыми. Многие 8-битные и 16-битные процессоры появились раньше 32- и 64-битных процессоров.
Компьютеры могут выполнять несколько миллиардов операций в секунду. Зацикливание 800 тыс. раз само по себе не будет проблемой.
Ответы 1
Ваш алгоритм ошибочен. Для каждого числа от 999 до 100 он затем выполняет цикл от 999 до 100 и проверяет первое число-палиндром. Но это не самое большое подобное число.
Это 906609, состоящее из 913 и 993. Ваш алгоритм никогда не достигает этой комбинации, потому что сначала он нашел комбинацию из 995 и гораздо меньшего числа.
Вы можете использовать свои циклы, но вам нужно продолжать цикл и сравнивать до максимума. Начнем с установки 0.
int main(void) {
int factorI = 0;
int factorJ = 0;
int max = 0;
for (int i = 999; i >= 100; i--) {
for (int j = 999; j >= 100; j--) {
int ij = i * j;
if (isPalindrome(ij) && ij > max) {
factorI = i;
factorJ = j;
max = ij;
}
}
}
printf("Done! Found palindrome.\n");
printf("i: %d\nj: %d\n", factorI, factorJ);
printf("PALINDROME: %d\n", max);
return 0;
}
Мы можем немного оптимизировать, не проверяя дубликаты. Если мы проверили 999, 995, нет смысла проверять 995, 999.
for (int i = 999; i >= 100; i--) {
for (int j = i; j >= 100; j--) {
int ij = i * j;
if (isPalindrome(ij) && ij > max) {
factorI = i;
factorJ = j;
max = ij;
}
}
}
Дальнейшая оптимизация
Мы можем понять, что если мы найдем соответствующее трехзначное значение j для данного значения i, если мы попробуем меньшее значение i, мы не получим больший продукт с меньшим значением j. Поэтому нам нужно динамически установить нижнюю границу для j.
int main(void) {
int factorI = 0;
int factorJ = 0;
int max = 0;
int min_j = 100;
for (int i = 999; i >= 100; i--) {
for (int j = i; j >= min_j; j--) {
int ij = i * j;
if (isPalindrome(ij) && ij > max) {
factorI = i;
factorJ = j;
max = ij;
min_j = j;
break;
}
}
}
printf("Done! Found palindrome.\n");
printf("i: %d\nj: %d\n", factorI, factorJ);
printf("PALINDROME: %d\n", max);
return 0;
}
Для трехзначных чисел это означает, что для i = 999, 998, 997, 996 нам придется проверять все вплоть до 100. Но для i = 995 мы найдем совпадение с j = 583. Мы обратите внимание, что это самый большой палидром, найденный на данный момент, с коэффициентами 995 и 583, и разорвите внутренний цикл. Теперь для i = 994, 993 мы выполняем цикл j только до 583, а не до 100 без необходимости. Для i = 993 мы находим совпадение по адресу 913. Это означает, что для оставшихся циклов мы повторяем j от:
992 -> 913
991 -> 913
990 -> 913
989 -> 913
988 -> 913
...
914 -> 913
913 -> 913
912 -> 913
Ой, посмотрите, все оставшиеся итерации i ничего не делают.
Функция isPalindrome
Это работает с вашим существующим isPalindrome, но это можно значительно улучшить, удалив динамическое выделение памяти, пройдя только половину строки и очистив поток управления в вашем цикле.
int isPalindrome(int number) {
char str[32];
sprintf(str, "%d", number);
size_t len = strlen(str);
for (size_t i = 0; i < len / 2; i++) {
if (str[i] != str[len - (i+1)])
return 0;
}
return 1;
}
:(. Я оставил сообщение, выделенное жирным шрифтом в конце моего вопроса, вы, вероятно, его не видели. В любом случае, хороший ответ! Обновлено: Думаю, это помогает объяснить ваш код, неважно.
О, нет! У меня больше нет причин использовать goto!
Кроме того, этого ответа я избегал в первую очередь. Я не хочу перебирать все 800 тысяч возможных факторов. Есть ли какой-нибудь способ избежать этого для целей компиляции? Скажем так... мой компьютер немного медленнее.
Вы можете перевернуть это с ног на голову. Начните с 999*999, что равно 998001, и ведите обратный отсчет, чтобы найти палиндромные числа, а затем определите, являются ли они произведением двух трехзначных множителей. Тогда вам нужно ответить на вопрос: будет ли это в 91392 раза дешевле, чем подход, показанный здесь?
Думаю, нет. Кажется, на моем компьютере все работало нормально.
Вы тщательно протестировали
isPalindrome, чтобы убедиться, что это работает? Обратите внимание: чтобы проверить, является ли строка палиндромом, вам нужно пройти только половину строки.