\documentclass[12pt]{article} \usepackage{times} \usepackage{fancyheadings} \pagestyle{fancy} \usepackage{pifont} % for fancy bullets \newcommand{\headerfont}{\fontfamily{phv}\fontseries{b}\fontshape{n}% \fontsize{10}{12pt}\selectfont} \newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}% \fontsize{12}{14pt}\selectfont} \newcommand{\largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{14}{16pt}\selectfont} \newcommand{\Largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{19}{21pt}\selectfont} \newcommand{\Largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}% \fontsize{19}{21pt}\selectfont} \newcommand{\largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}% \fontsize{14}{16pt}\selectfont} \newcommand{\mywidth}{6.0in} \newcommand{\lefthead}{CS1723: Data Structures, Assignment 1} \newcommand{\st}{\rule[-.8mm]{0mm}{2mm}} \newcommand{\longst}{\rule[-3mm]{0mm}{2mm}} \newcommand{\outerbaselinesep}{12.5pt} \topmargin 0.0in \oddsidemargin 0.25in \evensidemargin 0.25in \textwidth \mywidth \textheight 8.0in %10mm \parskip 2.5mm \fboxrule=0.3mm %%%%%%%%% Headings %%%%%%%%%%%%%%%%%%%%%%% \setlength{\headwidth}{\textwidth} % This shouldn't be needed. ?? %\setlength{\headrulewidth}{0pt} % to eliminate rule under header \newcommand{\currhead}{CS 1723, Assignment 3: Palindrome Primes, \today} \lhead{\footnotesize \currhead} \rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}\hspace{0.4mm}} \lfoot{} \chead{} \cfoot{} \rfoot{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%% % main font declaration %\timesroman %%%%%%%%%%%%%%%%%%%%%%%%% \sloppy %\thispagestyle{empty} \begin{center} %{\largebold The University of Texas at San Antonio \\ %Computer Science Program \\ %San Antonio, Texas 78249} \\ %\vspace{0.2in} {\largebold CS 1723, Data Structures \\ Fall Semester, 1998 \\ Programming Assignment 2, Due September 18, 1998 } \\ {\largeboldital Palindrome Primes} \end{center} \baselineskip=\outerbaselinesep {\bf The assignment:} For this assignment, you are to write a program which finds all integers less than 20000 which are prime numbers and which are base 10 palindromes at the same time. An integer is {\em prime} if no other integers divide evenly into it. (29 and 47 are primes, while 51 is not, since 3 divides evenly into 51.) An integer is a {\em palindrome} (to base 10) if its digits are the same written forwards or backwards. (13231 is a palindrome, while 13321 is not. 13331 is both a prime and a palindrome.) {\bf Checking that an integer is prime:} This is fairly easy. Write a function with prototype {\tt int isprime(int n);} \noindent {\tt isprime} should check each integer {\tt i} less than or equal to {\tt sqrt(n)} to see if {\tt i} divides evenly into {\tt n}. This can be done by checking if \verb+(n%i) == 0+. Don't forget to include \verb++ and to use {\tt -lm} at the end of the {\tt lint} and {\tt cc} commands. Of course return 0 or false if {\tt n} is not a prime and return 1 if {\tt n} is a prime. {\bf Checking that an integer is a palindrome:} For this part you are required to use a stack and a queue, and to use the following function. (There are easier ways to check if an integer is a palindrome, but for this assignment we are interested in implementing a stack and a queue.) \begin{verbatim} /* ispalin: checks base 10 digits of n, to see if * they are the same forwards and backwards. * Uses both a stack and a queue. */ int ispalin(int n) { int digit, digs, digq; int returnval = 1; while (n != 0) { digit = n%10; push(digit); insert(digit); n = n/10; } while (!emptys()) { digs = pop(); digq = delete(); if (digs != digq) returnval = 0; } return returnval; } \end{verbatim} \noindent {\tt ispalin} generates the decimal digits of {\tt n} one at a time, pushes each digit on a stack and also inserts each digit into a queue. Later when each digit is popped and removed, respectively, the queue's digits will come out in the order they went in, while the stack's digits will come out in the opposite order. Thus when popping and removing, if all the digits are the same then the number must be a base 10 palindrome. {\bf The stack:} For your stack, you must use two separate files, {\tt stack.h} and {\tt stack.c}, and these can be almost the same as what was handed out in class, except that the {\tt StackType} should be {\tt int}, and the {\tt empty} and {\tt full} functions should be renamed {\tt emptys} and {\tt fulls} (so that they won't be the same as those for the queue.). {\bf The queue:} The queue should be an array-based circular queue modeled after the stack. You can copy and modify the stack files to get two new files {\tt queue.h} and {\tt queue.c} for the queue. The queue header file {\tt queue.h} should look like: \begin{verbatim} /* * queue.h -- queue header file */ typedef int Queuetype; Queuetype delete(void); void insert(Queuetype); int emptyq(void); int fullq(void); \end{verbatim} The size of the array used for this queue must be no more than 10, so that you will be demonstrating that the wrap-around aspect of your queue works. {\bf The whole program:} Name the file with the main function {\tt palin.c}. It also includes the functions {\tt isprime} and {\tt ispalin}. Your whole program should consist of 5 separate files. Here is a simple makefile that you could use. (Don't forget to ues a ``TAB'' character before the {\tt cc} and the {\tt lint} below.) \begin{verbatim} palin: palin.c stack.c stack.h queue.c queue.h cc -g -o palin palin.c stack.c queue.c -lm lint: lint -m -u palin.c stack.c queue.c -lm \end{verbatim} \noindent In the main function you should check integers from 2 to 20000 to see which ones are both primes and palindromes. (Hint: there are none between 1000 and 10000, but, for example, 17471 is both a prime and a palindrome.) {\bf What to turn in:} Just turn in a listing with the five files {\tt palin.c}, {\tt stack.c}, {\tt stack\_int.h}, {\tt queue.h}, and {\tt queue.c} along with the integer answers (I got 46 of them) concatenated together. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{'thatsall'} \end{document}