Project Euler – 4

解决 Project Euler – 问题 4。

/**
 * Problem 4
 * Largest palindrome product
 *
 * A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
 * Find the largest palindrome made from the product of two 3-digit numbers.
 */

#include <stdio.h>

#include <stdbool.h>
#include <stdlib.h>

#include <string.h>   // strncpy
#include <math.h>     // pow (ps. -lm)

#define element_t unsigned long long

static element_t calc_ele_len(const element_t num)
{
  element_t len = 0;
  element_t num_tmp = num;

  for (len = 1, num_tmp /= 10; num_tmp > 0; len++, num_tmp /= 10);
  return len;
}

static bool is_even(const element_t num)
{
  return num % 2 == 0;
}

static bool is_palindromic(const element_t num)
{
  const element_t num_str_len = calc_ele_len(num);
  const element_t num_str_len_half = num_str_len / 2;
  char * num_str = malloc(sizeof(char) * (num_str_len + 1));
  char * num_str_l = malloc(sizeof(char) * (num_str_len_half + 1));
  char * num_str_r = malloc(sizeof(char) * (num_str_len_half + 1));

  // copy
  sprintf(num_str, "%lld", num);

  strncpy(num_str_l, num_str, num_str_len_half);
  strncpy(num_str_r,
          is_even(num_str_len) ? num_str + num_str_len_half : num_str + num_str_len_half + 1,
          num_str_len_half);

  for (element_t i = 0; i < num_str_len_half; i++)
    if (num_str_l[i] != num_str_r[num_str_len_half - i - 1])
    {
      free(num_str_r);
      free(num_str_l);
      free(num_str);
      return false;
    }

  free(num_str_r);
  free(num_str_l);
  free(num_str);

  return true;
}

static element_t find_largest_palindrome_product(const element_t len)
{
  const element_t start = pow(10.0, len - 1);
  const element_t end = pow(10.0, len) - 1;
  element_t largest_palindrome = 0;

  for (element_t i = start; i <= end; i++)
    for (element_t j = start; j <= end; j++)
    {
      element_t tmp = i * j;

      if (is_palindromic(tmp) && tmp > largest_palindrome)
        largest_palindrome = tmp;
    }
  return largest_palindrome;
}


int main(int argc, char const *argv[])
{
  if (argc != 2) return EXIT_FAILURE;
  const element_t n = atoll(argv[1]);

  printf("the largest palindrome made from the product of two %lld-digit numbers is %lld.n",
    n, find_largest_palindrome_product(n));

  return EXIT_SUCCESS;
}

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s