当前位置：文档之家 › 给定一个字符串,求这个字符串的最大回文数

给定一个字符串,求这个字符串的最大回文数

  • 格式：doc
  • 大小：108.50 KB
  • 文档页数：6

题目：回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际应用中比较广泛，下面介绍几个回文的问题。 首先我们要介绍一个什么叫回文数：回文，就是指一个字符串顺着读和反着读都是一样的字符串，例如madam，你我你，我爱我 等等一些列的字符串 1、首先来判断一下一个字符串是否是回文字符串：

[java] view plaincopyprint?  public int palindromeNumber(String s, int low, int high) {  if (low == high)  return 1;  else if (low < high) {  if (s.charAt(low) == s.charAt(high) && (high - low) == 1) //防止出现abba等情况  return 1;  if (s.charAt(low) == s.charAt(high) && (high - low) != 1) //这是类似aba的情况  return palindromeNumber(s, low + 1, high - 1);  else  return 0;  } else  return 0;  }

上面的这个方法，如果输入的字符串是回文字符串的话，则输出1，如果不是的话，输出0， 2、已经明白了如何判断一个字符串是否是回文数，接下来我们就要求出一个给定字符串中最大的回文数是多少，就是把这个回文数的长度打出来

[java] view plaincopyprint?  package programmer;   import java.util.Scanner;   /*  * 回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也  * 比较广泛，而且也是面试题中的常客，所以本文就结合几个典型的例子来体味下回文之趣。  * 回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如 madam、  * 我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多  * 有趣的回文诗呢  */  public class PalindromeNumber {   public int palindromeNumber(String s, int low, int high) {  if (low == high)  return 1;  else if (low < high) {  if (s.charAt(low) == s.charAt(high) && (high - low) == 1)  return 1;  if (s.charAt(low) == s.charAt(high) && (high - low) != 1)  return palindromeNumber(s, low + 1, high - 1);  else  return 0;  } else  return 0;  }   /*  * 这里求一个字符串中的最长回文字符串的长度，我们使用了枚举的方法，但是这 种方法的时间复杂度还是很大的，浪费了很多不必要的时间和判断，比如当判断  * 子串 不是回文时， 就不必要再判断包含本子串的父串了  */  public int maxPalindrome1(String s) {  int len = 0, max = 0;  for (int i = 0; i < s.length(); i++) {  for (int j = s.length() - 1; j >= i; j--) {  if (palindromeNumber(s, i, j) == 1) {  len = j - i + 1;  }  if (max < len)  max = len;  }  }  return max;  }   public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  String s = sc.nextLine();  System.out.println(new PalindromeNumber().palindromeNumber(s, 0,  s.length() - 1));  System.out.println(new PalindromeNumber().maxPalindrome1(s));  }  } 上面的思想也十分简单，就是逐个遍历，显然这是十分耗费时间的，时间复杂度为O(n*n*n)，因为还要判断这个是否是回文数，所以比较浪费时间。接下来我们提供一种比较有建设性的方法。 3、我们知道回文数是正着读和反着读是一样的，就是说对于一个给定的字符串，如果我们将这个字符串逆置的话，我们就会发现两个字符串有一个最长的连续相同的子序列，则这个连续的最长的共同子序列就是我们要求的回文数，例如：abcabcba，反过来就是abcbacba，显然我们发现两个字符串连续的最长的共同子序列就是abcba，而abcba就是我们索要求的最长的回文数。 下面是这个源代码：

[java] view plaincopyprint?  package programmer;   import java.util.Scanner;   public class PalindromeNumber1 {  StringContain obj = new StringContain();   public int Max(String s1, String s2) {  int max = 0;  for (int i = 0; i < s1.length(); i++) {  for (int j = s2.length(); j > i; j--) {  if (obj.stringContain(s1, s2.substring(i, j)) == 1) {  if (max < j - i)  max = j - i;  }  }  }  return max;  }   public String reverseString(String s) {  char[] c = new char[s.length()];  c = s.toCharArray();  for (int i = 0, j = c.length - 1; i < j; i++, j--) {  char ch = c[i];  c[i] = c[j];  c[j] = ch;  }  return String.valueOf(c);  }   public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  String s1 = sc.nextLine();  // System.out.println(s1.subSequence(0, s1.length() - 1));  String s2 = new PalindromeNumber1().reverseString(s1);  System.out.println(s2);  System.out.println(new PalindromeNumber1().Max(s1, s2));  }  }

而其中我们用到了stringContain()方法，这是我写的判断一个字符串是否包含另外一个字符串的算法，代码如下：

[java] view plaincopyprint?  package programmer;   import java.util.Scanner;   /*  * 这是判断字符串s1中是否包含字符串s2  */   public class StringContain {  public int stringContain(String s1, String s2) {  int i, j;  for (i = 0, j = 0; i < s1.length() && j < s2.length();) {  if (s1.charAt(i) != s2.charAt(j)) {  if (j != 0)  j = 0;  else  i++;  } else {  i++;  j++;  }  }  if (j == s2.length())  return 1;  return 0;

合集下载

c语言 回文数 栈

c语言 回文数 栈

c语言回文数栈回文数是指正读和反读都相同的整数。

例如，121、12321都是回文数。

在计算机科学中，我们可以使用栈来判断一个数是否为回文数。

我们需要明确一点：回文数是十进制下的概念，而计算机中的数是以二进制表示的。

因此，在计算机中判断一个数是否为回文数，我们需要先将其转换为字符串。

接下来，我们可以使用栈来进行判断。

栈是一种先进后出的数据结构，我们可以利用栈的特性来判断字符串是否为回文。

具体的算法如下：1. 将整数转换为字符串。

2. 创建一个空栈。

3. 将字符串的每个字符依次入栈。

4. 将栈中的字符出栈，并与字符串中的字符逐个比较。

5. 如果所有字符都相同，则该字符串是回文数；否则，不是回文数。

下面我们用C语言来实现这个算法：```c#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;} Stack;// 初始化栈void initStack(Stack *s) {s->top = -1;}// 入栈void push(Stack *s, char c) { s->data[++(s->top)] = c;}// 出栈char pop(Stack *s) {return s->data[(s->top)--]; }// 判断回文数int isPalindrome(int num) {char str[MAX_SIZE];sprintf(str, "%d", num); // 将整数转换为字符串 int len = strlen(str);Stack s;initStack(&s);// 将字符串的每个字符入栈for (int i = 0; i < len; i++) {push(&s, str[i]);}// 将栈中的字符和字符串中的字符逐个比较for (int i = 0; i < len; i++) {if (pop(&s) != str[i]) {return 0; // 不是回文数}}return 1; // 是回文数}int main() {int num;printf("请输入一个整数：");scanf("%d", &num);if (isPalindrome(num)) {printf("%d是回文数。

c语言回文素数的判断

c语言回文素数的判断

c语言回文素数的判断1. 什么是回文素数？回文素数是指既是回文数又是素数的自然数。

回文数是指一个数从左往右读与从右往左读相同的数，比如131、1221、12321等。

素数是指只能被1和自身整除的自然数，比如2、3、5、7、11等。

2. 为什么要判断回文素数？回文素数在数学上是一个非常有趣的概念，它既具有回文数的特点，又具有素数的特点。

判断回文素数不仅可以提高我们对数学的认识，还能在编程中发挥重要作用，比如在密码学领域、信息安全领域等。

3. 怎样判断回文素数？判断回文素数需要进行两个步骤：首先判断该数是否是回文数，然后再判断该数是否是素数。

判断回文数判断回文数的方法有多种，下面介绍两种：方法一：用字符串这个方法是将整数转换为字符串，然后判断字符串的首尾字符是否相等，依次向中间遍历。

示例代码：```cinclude <stdio.h>include <string.h>int isPalindrome(int n) {char str[20];sprintf(str, "%d", n); // 将整数转换为字符串int len = strlen(str);for (int i = 0; i < len / 2; i++) {if (str[i] != str[len - i - 1]) {return 0; // 不是回文数}}return 1; // 是回文数}```方法二：用数字这个方法是通过计算整数的各位数和对比首尾数，依次向中间遍历。

示例代码：```cint isPalindrome(int n) {if (n < 0 || (n != 0 && n % 10 == 0)) {return 0; // 负数或末尾为0的数都不是回文数}int sum = 0;while (n > sum) {sum = sum * 10 + n % 10;n /= 10;}return n == sum || n == sum / 10; // 判断首位是否相等}```判断素数判断素数的方法也有多种，下面介绍两种：这个方法是从2到n-1枚举所有自然数，看是否能整除n。

构造回文子串

构造回文子串

构造回文子串构造回文子串回文子串是指正读和反读都一样的字符串，比如“level”、“racecar”等等。

对于许多算法问题而言，都需要对输入的字符串进行回文子串的处理，因此如何快速构造回文子串成为了一个重要的课题。

下面将针对回文子串的构造方法进行分类介绍。

1. 中心扩展法中心扩展法是最简单、最直接的回文子串构造算法，其思路是将每一个字符作为中心向两侧扩展，并判断是否是回文子串。

该算法时间复杂度为O(n^2)，其中n为字符串长度。

2. 马拉车算法马拉车算法是一种高效的回文子串构造算法，其基本思想是通过已知回文子串的对称性进行快速扩展。

首先，在原字符串的每个位置插入一个不同的字符，用“#”分隔每个字符，得到一个新的字符串。

例如，原字符串“level”由此变成了“#l#e#v#e#l#”。

接下来，使用“Palindrome Array”数组记录以每个字符为基准可以扩展的最长回文子串的长度，同时记录此时最右侧的回文子串的边界R。

为了避免出界问题，可以在每个字符的左右两侧都加上无限制的字符（例如“#”），初始化Palindrome Array数组时，置所有的元素为0。

在计算过程中，可以首先通过对称性取得与当前字符i的对称点j的“Palindrome Array[i]”的值，然后将其与j到R这一部分的长度相加，得到以i为中心的最大回文子串长度，并更新Palindrome Array[i]的值。

最后，扫描整个Palindrome Array数组，取得最大值，并计算奇偶性确定回文子串的长度，从而在原字符串中找到构成回文子串的部分。

该算法的时间复杂度为O(n)，在处理大规模串的回文子串时，极具优势。

3. Manacher算法Manacher算法是对马拉车算法的一次改进，主要在寻找对称点上采用了更高效的方法。

Manacher算法在时间复杂度上与马拉车算法相同（O(n)），但更为简单直观。

Manacher算法仍然将原串插入分隔符“#”中，但是对Palindrome Array的计算过程采用了两个指针，分别指向一个最靠右的已知回文串，和一个最靠右的已知回文串的中心。

C语言试题+提纲

C语言试题+提纲

计算机应用（C语言）：100分一、选择题；二填空题；三、判断题；四、根据程序写出结果；五、补充完善程序；根据题目要求完善程序；计算机应用上机（C语言）：100分共3道大题，其中自定义函数并调用一定存在，主要参考实验、典型例题以及少量自编考试题。

计算机应用和应用上机（C语言）fx提纲第一章1、C语言的特点2、C语言的基本操作与常使用的快捷键等visual Studio6.0环境：原程序、编译、组建和运行后程序的后缀和快捷方式分别为？？（visual C++6.0环境下执行相对应的操作后左下角显示后缀名）第二章1、算法的定义与特点一个算法应该具有以下特点：___、______，零个或多个输入,一个或多个输出,___ __。

2、表示算法的常用方法3、结构化程序设计的基本结构结构化程序设计的三种基本程序结构为_______、___ _____、___ _____。

第三章1、常用的数据类型（int，float和char）以及不同数据类型占用的字节数和有效数字和有效范围（输出结果）visual C++6.0中数据类型float的数占的字节数为( ) 。

A)1 B)2C)4 D)32、正确与错误的标识符的判定——正确条件：（1）只能使用字母、数字和下划线_；（2）首字符只能是字母或下划线_；（3）不能使用关键字作为标识符；正确的自定义标识符是（）A) #33 B) a>bC) tt D) 3days3、常量、变量等的定义4、字符常量的特殊符号（如\）和转义符号的正确判断——（1）注意特殊转移字符如\n,\t,\v,\\,\‘等；（2）注意\ddd和\xhh，其中ddd只能是3位八进制的数0-7，hh是2位16进制的数，0-9和A，B，C，D，E，F错误的转义字符是( ) 。

A)'\091' B) '\\'C) '\0' D) '\'''以下常用转义符号代表换行的是( ) 。