C代写:palindrome检测与cellular automaton仿真

本次作业有两个问题: 用C实现字符数组中palindrome检测, 用C实现元胞自动机仿真。

Do the following programming problems. You will end up with at least one code file per problem. Submit your program source (and any other needed files) by sending mail to bmassing@cs.trinity.edu with each file as an attachment. Please use a subject line that mentions the course and the assignment (e.g., ``csci 1120 hw 7’’ or ``LL hw 7’’). You can develop your programs on any system that provides the needed functionality, but I will test them on one of the department’s Linux machines, so you should probably make sure they work in that environment before turning them in.

  1. (10 points) Write a C program that prompts the user for a single line of text and prints whether it is a palindrome, i.e., whether it’s ``the same’’ backwards as forwards, according to the following rules:

    • Only letters and digits count; spaces, punctuation, etc., do not.
    • Case of letters is not significant (‘A’ and ‘a’ are considered the same).

    The program should also print an error message if the text supplied by the user doesn’t fit into the array you use to represent the input string.

    Here are some sample executions:

    [bmassing@dias04]$ ./a.out 
    enter a line of text:
    abcd dcba
    input 'abcd dcba'
    a palindrome
    
    [bmassing@dias04]$ ./a.out 
    A man, a plan, a canal -- Panama!
    input 'A man, a plan, a canal -- Panama!'
    a palindrome
    
    [bmassing@dias04]$ ./a.out 
    enter a line of text:
    abcd 12 bcda
    input 'abcd 12 dcba'
    not a palindrome
    
    [bmassing@dias04]$ ./a.out 
    enter a line of text:
    abcd 1221 dcba
    input 'abcd 1221 dcba'
    a palindrome
    

    Hints:

    • You may find sample programs echo-line.c and simple-strings.c helpful.
    • You may find library functions such as isalpha() and tolower helpful.
  2. (15 points) Your mission for this assignment is to first complete and then modify a starter program that plays mathematician John Conway’s ``Game of Life’’, described below. (You can also find more information on the Web. The Wikipedia articleeems good.)

    The Game of Life is not so much a game in the usual sense as a set of rules for something called a cellular automaton: There are no players, and once the initial configuration is established, everything that happens is determined by the game’s rules. The game is ``played’’ on a board consisting of a rectangular grid of cells. Some cells are ``live’’ (contain a simulated organism); others are ``dead’’ (empty). At each step, a new configuration is computed from the old configuration according to the following rules:

    • For each cell, we look at its eight neighbors (top, bottom, left, right, and the four diagonal neighbors) and count the number of cells that are live. Note that this count is based on the configuration at the start of the time step.
    • A dead cell with exactly three live neighbors becomes live; otherwise it stays dead.
    • A live cell with two or three live neighbors stays live; otherwise it becomes dead (of isolation or overcrowding).
    • What do to with cells at the boundary of the board is tricky; to me the option that makes the most sense is to only consider the cells that exist; so for example a cell at one of the four corners only has three neighbors.

    To visualize how this works … I found a few Web sites that let you ``play’’ online, but none I found immediately appealing. I have a version that uses text-based graphics that you should be able to use on our classroom/lab machines. Download file game, tell Linux it’s an executable file with the command chmod u+x game, and run it with the command ./game. If you’re curious, the program is written in C++ using a library called ncurses to do text-based graphics.

    To implement the basic algorithm in a program, you pretty much need to use 2D arrays. Writing a complete program is straightforward but more than I want to ask you to do; instead I am providing starter code that does everything but the actual update of the grid: game-of-life-starter.c. The program takes two command-line arguments, the name of a file containing an initial configuration and the number of steps to ``play’’; it prints the initial configuration and then updated configurations for the specified number of steps. Sample output for input files game-of-life-in1.txt and game-of-life-in2.txt:

    [bmassing@dias04]$ ./a.out game-of-life-in1.txt 4
    Initial board:
    . . . . . . 
    1 1 1 . . . 
    . . . . . . 
    . . . . 1 . 
    . . . . 1 . 
    . . . . 1 . 
    
    Board after step 1:
    . 1 . . . . 
    . 1 . . . . 
    . 1 . . . . 
    . . . . . . 
    . . . 1 1 1 
    . . . . . . 
    
    Board after step 2:
    . . . . . . 
    1 1 1 . . . 
    . . . . . . 
    . . . . 1 . 
    . . . . 1 . 
    . . . . 1 . 
    
    Board after step 3:
    . 1 . . . . 
    . 1 . . . . 
    . 1 . . . . 
    . . . . . . 
    . . . 1 1 1 
    . . . . . . 
    
    Board after step 4:
    . . . . . . 
    1 1 1 . . . 
    . . . . . . 
    . . . . 1 . 
    . . . . 1 . 
    . . . . 1 . 
    
    [bmassing@dias04]$ ./a.out game-of-life-in2.txt 4
    Initial board:
    . . . . . . . . 
    . 1 1 . . . . . 
    . 1 1 . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . 1 1 . 
    . . . . . 1 1 . 
    . . . . . . . . 

    Board after step 1:
    . . . . . . . . 
    . 1 1 . . . . . 
    . 1 1 . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . 1 1 . 
    . . . . . 1 1 . 
    . . . . . . . . 

    Board after step 2:
    . . . . . . . . 
    . 1 1 . . . . . 
    . 1 1 . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . 1 1 . 
    . . . . . 1 1 . 
    . . . . . . . . 

    Board after step 3:
    . . . . . . . . 
    . 1 1 . . . . . 
    . 1 1 . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . 1 1 . 
    . . . . . 1 1 . 
    . . . . . . . . 

    Board after step 4:
    . . . . . . . . 
    . 1 1 . . . . . 
    . 1 1 . . . . . 
    . . . . . . . . 
    . . . . . . . . 
    . . . . . 1 1 . 
    . . . . . 1 1 . 
    . . . . . . . . 

For this assignment you will turn in two programs:

The first program just fills in the missing part of the program (look for comment \`\`FIXME'') so that it works as intended.

The second program adapts the first one to experiment with generating the initial board \`\`randomly'' rather than reading it in from a file and observing how the game evolves with different board sizes and parameters for generating \`\`random'' data. Your program should get all its input from command-line arguments:

-   Size of board (a `long`).
-   Seed for random number sequence (a `long`).
-   Fraction of cells that should be \`\`live'' initially (a `double`) (not really a great name, explained better later).
-   Number of steps (a `long`).
-   Optionally, the word \`\`print''.

The program should then work as follows:

-   Generate an initial configuration by first calling `srand()` and then calling `rand()` once per cell, setting the cell to `true` based on whether what `rand()` returns, divided by `RAND_MAX`, is less than the specified fraction.
-   Count and print the number of cells that are \`\`live'', and print the board if the \`\`print'' option was specified.
-   For each step, update the board (no change from first program), but then rather than always printing the new board, count and print the number of cells that are \`\`live'', and print the board if the \`\`print'' option was specified.

(My idea here is that such a program could be a prototype for something that would allow you to try out more-sophisticated ways of generating \`\`random'' configurations and observing how they evolve.)

Here are some sample executions:

    [bmassing@dias02]$ ./a.out 6 5 .5 1 print
    28 live cells at start (fraction 0.777778)
    Initial board:
    1 1 . 1 1 1 
    1 1 1 . 1 1 
    . 1 1 1 1 1 
    1 1 1 1 1 1 
    1 . . 1 1 . 
    1 . 1 1 . 1 

    8 live cells after step 1 (fraction 0.222222)
    Board after step 1:
    1 . . 1 . 1 
    . . . . . . 
    . . . . . . 
    1 . . . . . 
    1 . . . . . 
    . 1 1 1 . . 



    [bmassing@dias02]$ ./a.out 6 7 .5 1 print
    18 live cells at start (fraction 0.500000)
    Initial board:
    1 . . 1 1 . 
    . 1 . 1 . 1 
    . . . 1 1 . 
    . 1 1 1 1 . 
    1 1 1 . 1 1 
    1 . . . . . 

    11 live cells after step 1 (fraction 0.305556)
    Board after step 1:
    . . 1 1 1 . 
    . . . . . 1 
    . 1 . . . 1 
    1 . . . . . 
    1 . . . 1 1 
    1 . . . . . 

    (different seeds give different configurations)



    [bmassing@dias02]$ ./a.out 6 5 .25 1 print
    9 live cells at start (fraction 0.250000)
    Initial board:
    . 1 . 1 1 1 
    . . . . 1 . 
    . 1 . . . . 
    . . . . . . 
    1 . . . . . 
    . . 1 . . 1 

    7 live cells after step 1 (fraction 0.194444)
    Board after step 1:
    . . . 1 1 1 
    . . 1 1 1 1 
    . . . . . . 
    . . . . . . 
    . . . . . . 
    . . . . . . 

    (smaller fraction gives fewer live cells)



    [bmassing@dias02]$ ./a.out 100 5 .5 10 
    5141 live cells at start (fraction 0.514100)
    2647 live cells after step 1 (fraction 0.264700)
    2453 live cells after step 2 (fraction 0.245300)
    2437 live cells after step 3 (fraction 0.243700)
    2265 live cells after step 4 (fraction 0.226500)
    2181 live cells after step 5 (fraction 0.218100)
    2127 live cells after step 6 (fraction 0.212700)
    2001 live cells after step 7 (fraction 0.200100)
    1873 live cells after step 8 (fraction 0.187300)
    1852 live cells after step 9 (fraction 0.185200)
    1784 live cells after step 10 (fraction 0.178400)



    [bmassing@dias02]$ ./a.out 100 5 .25 10
    2497 live cells at start (fraction 0.249700)
    2789 live cells after step 1 (fraction 0.278900)
    2338 live cells after step 2 (fraction 0.233800)
    2382 live cells after step 3 (fraction 0.238200)
    2243 live cells after step 4 (fraction 0.224300)
    2137 live cells after step 5 (fraction 0.213700)
    2158 live cells after step 6 (fraction 0.215800)
    2145 live cells after step 7 (fraction 0.214500)
    2028 live cells after step 8 (fraction 0.202800)
    2035 live cells after step 9 (fraction 0.203500)
    1899 live cells after step 10 (fraction 0.189900)

*Hints:*

-   For parsing command-line arguments, remember that to get a numeric value you should call `strtol` or `strtod`, and to compare two strings you need `strcmp` rather than `==`.
-   You should not need to make a lot of changes to your first program; what you need to do is:
    -   Add code to parse the new command-line arguments.
    -   Replace the function that reads the initial configuration from a file with one that generates it \`\`randomly''.
    -   Add a function to count the number of \`\`live'' cells.
    -   Change the code that always prints the board so that instead it prints the count of live cells and optionally the board.


Footnotes

… apply).1
Credit where credit is due: I based the wording of this list on a posting to a SIGCSE mailing list. SIGCSE is the ACM’s Special Interest Group on CS Education.


Berna Massingill
2017-11-15

kamisama wechat
KamiSama