题目：汉诺塔问题

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。

输入格式

圆盘数 起始柱 目的柱 过度柱

输出格式

移动汉诺塔的步骤
每行显示一步操作，具体格式为：
盘片号: 起始柱 -> 目的柱
其中盘片号从 1 开始由小到大顺序编号。

输入样例

3
a c b

输出样例

1: a -> c
2: a -> b
1: c -> b
3: a -> c
1: b -> a
2: b -> c
1: a -> c

我的代码

#include<stdio.h>void move(int n,char a,char b,char c)
{
    if(n==1)
        printf("\t%c->%c\n",a,c);
    else
    {
        move(n-1,a,c,b);                printf("\t%c->%c\n",a,c);
        move(n-1,b,a,c);
    }
}main()
{
    int n;
    printf("请输入数字n(要移动的块数)以解决n阶汉诺塔问题：");
    scanf("%d",&n);
　　move(n,'a','b','c');
    while(1);
}

解题流程图

本题遇见的问题与解决办法

到处都是问题，达到了无法用言语表达的地步

运行结果截图

题目：估值一亿的AI核心代码

上图来自网络

本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：

无论用户说什么，首先把对方说的话在一行中原样打印出来；

消除原文中多余空格：把相邻单词间的多个空格换成 1 个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；

把原文中所有大写英文字母变成小写，除了 I；

把原文中所有独立的 can you、could you 对应地换成 I can、I could—— 这里“独立”是指被空格或标点符号分隔开的单词；

把原文中所有独立的 I 和 me 换成 you；

把原文中所有的问号 ? 换成惊叹号 !；

在一行中输出替换后的句子作为 AI 的回答。

输入格式：

输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000 个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。

输出格式：

按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。

输入样例：

6
Hello ?
 Good to chat   with you
can   you speak Chinese?
Really?
Could you show me 5
What Is this prime? I,don 't know

输出样例：

Hello ?
AI: hello!
 Good to chat   with you
AI: good to chat with you
can   you speak Chinese?
AI: I can speak chinese!
Really?
AI: really!
Could you show me 5
AI: I could show you 5
What Is this prime? I,don 't know
AI: what Is this prime! you,don't know

我的代码

#include<iostream>
#include<ctype.h>
#include<vector>
#include<string>using namespace std;vector<string>v;int main()
{
    int n;
    string s;
    cin>>n;
    getchar();
    while(n--)
    {
        getline(cin,s);
        cout<<s<<endl<<"AI: ";
        int len=s.length();        for(int i=0;i<len;i++)
        {
        if(s[i]=='?')
          s[i]='!';
        else if(isupper(s[i])&&s[i]!='I')
          s[i]=tolower(s[i]);
 }v.clear();        for(int i=0;i<len;)
        {
        string tmp="";
        if(isalpha(s[i]))
        {
        while(i<len&&isalpha(s[i])) tmp+=s[i++];
}
else if(isdigit(s[i]))
{
while(i<len&&isdigit(s[i])) tmp+=s[i++];
}
else if(s[i]==' ')
{
tmp=" ";
while(i<len&&s[i]==' ') i++;
}
else
{
tmp+=s[i];
i++;if(v.size()>0&&v.back()==" ") v.pop_back();
}
if(tmp==" "&&(v.empty()||i==len)) continue;
v.push_back(tmp);
}
for(int i=0;i<v.size();i++)
  if(v[i]=="I"||v[i]=="me")
    v[i]="you";
  else if(v[i]=="you")
  {  if(i<2||!(v[i-1].length()==1&&(!isalnum(v[i-1][0])))) continue;
  if(v[i-2]=="can")
    v[i-2]="I",v[i]="can";
  else if(v[i-2]=="could")
    v[i-2]="I",v[i]="could";
  }for(int i=0;i<v.size();i++)
  cout<<v[i];
cout<<endl;
    }
    return 0;
}

解题流程图

本题遇见的问题与解决办法

到处都是问题，达到了无法用言语表达的地步

运行结果截图

题目：***八皇后问题

在国际象棋中，皇后是最厉害的棋子，可以横走、直走，还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题：即在 8 × 8 的棋盘上摆放八个皇后，使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。

现在我们把棋盘扩展到 n × n 的棋盘上摆放 n 个皇后，请问该怎么摆？请编写程序，输入正整数 n，输出全部摆法(棋盘格子空白处显示句点“.”，皇后处显示字母“Q”，每两格之间空一格)。

输入格式

正整数 n (0 ＜ n ≤ 12)

输出格式

若问题有解，则输出全部摆法(两种摆法之间空一行)，否则输出 None。

要求：试探的顺序逐行从左往右的顺序进行，请参看输出样例2。

输入样例1

3

输出样例1

None

输入样例2

6

输出样例2

. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .. . Q . . .
. . . . . Q
. Q . . . .
. . . . Q .
Q . . . . .
. . . Q . .. . . Q . .
Q . . . . .
. . . . Q .
. Q . . . .
. . . . . Q
. . Q . . .. . . . Q .
. . Q . . .
Q . . . . .
. . . . . Q
. . . Q . .
. Q . . . .

我的代码

#include <stdio.h>
int Queenes[8]={0},Counts=0;
int Check(int line,int list){    for (int index=0; index<line; index++) {        int data=Queenes[index];        if (list==data) {
            return 0;
        }        if ((index+data)==(line+list)) {
            return 0;
        }            return 0;
        }
    }    return 1;
}void print()
{
    for (int line = 0; line < 8; line++)
    {
        int list;
        for (list = 0; list < Queenes[line]; list++)
            printf("0");
        printf("#");
        for (list = Queenes[line] + 1; list < 8; list++){
            printf("0");
        }
        printf("\n");
    }
    printf("================\n");
}
void eight_queen(int line){    for (int list=0; list<8; list++) {        if (Check(line, list)) {            Queenes[line]=list;            if (line==7) {                Counts++;                print();                Queenes[line]=0;
                return;
            }            eight_queen(line+1);            Queenes[line]=0;
        }
    }
}
int main() {    eight_queen(0);
    printf("摆放的方式有%d种",Counts);
    return 0;
}

解题流程图

本题遇见的问题与解决办法

到处都是问题，达到了无法用言语表达的地步

运行结果截图

何为数组指针？

数组指针，指的是数组名的指针，即数组首元素地址的指针。即是指向数组的指针。例：int (*p)[10]; p即为指向数组的指针，又称数组指针。

解释来源于百度百科

比如。。。

#include "stdafx.h"int main()
{
//一维数组
int a[5] = { 1, 2, 3, 4, 5 };
//步长为5的数组指针，即数组里有5个元素
int (*p)[5];
//把数组a的地址赋给p，则p为数组a的地址，则*p表示数组a本身
p = &a;//%p输出地址, %d输出十进制
//\n回车
//在C中，在几乎所有使用数组的表达式中，数组名的值是个指针常量，也就是数组第一个元素的地址，它的类型取决于数组元素的类型。
printf("%p\n", a); //输出数组名，一般用数组的首元素地址来标识一个数组，则输出数组首元素地址
printf("%p\n", p); //根据上面，p为数组a的地址，输出数组a的地址
printf("%p\n", *p); //*p表示数组a本身，一般用数组的首元素地址来标识一个数组
printf("%p\n", &a[0]); //a[0]的地址
printf("%p\n", &a[1]); //a[1]的地址
printf("%p\n", p[0]); //数组首元素的地址
printf("%d\n", **p); //*p为数组a本身，即为数组a首元素地址，则*(*p)为值，当*p为数组首元素地址时，**p表示首元素的值1
printf("%d\n", *p[0]); //根据优先级，p[0] 表示首元素地址，则*p[0]表示首元素本身，即首元素的值1
printf("%d\n", *p[1]); //为一个绝对值很大的负数，不表示a[1]...表示什么我还不知道//将二维数组赋给指针
int b[3][4];
int(*pp)[4]; //定义一个数组指针，指向含4个元素的一维数组
pp = b; //将该二维数组的首地址赋给pp，也就是b[0]或&b[0]，二维数组中pp=b和pp=&b[0]是等价的
pp++; //pp=pp+1，该语句执行过后pp的指向从行b[0][]变为了行b[1][]，pp=&b[1]int k;
scanf_s("%d", &k);    return 0;
}

何为指针数组？

在C语言和C++语言中，数组元素全为指针的数组称为指针数组。

一维指针数组的定义形式为：“类型名 *数组标识符[数组长度]”。

例如，一个一维指针数组的定义：int *ptr_array[10]。

解释来源于百度百科

例如。。。

#include "stdafx.h"int main()
{
int a = 1;
int b = 2;
int *p[2];
p[0] = &a;
p[1] = &b;printf("%p\n", p[0]); //a的地址
printf("%p\n", &a); //a的地址
printf("%p\n", p[1]); //b的地址
printf("%p\n", &b); //b的地址
printf("%d\n", *p[0]); //p[0]表示a的地址，则*p[0]表示a的值
printf("%d\n", *p[1]); //p[1]表示b的地址，则*p[1]表示b的值//将二维数组赋给指针数组
int *pp[3]; //一个一维数组内存放着三个指针变量，分别是p[0]、p[1]、p[2]，所以要分别赋值
int c[3][4];
for (int i = 0; i<3; i++)
pp[i] = c[i];int k;
scanf_s("%d", &k);    return 0;
}

何为指针函数？

指针函数是一个函数。函数都有返回类型（如果不返回值，则为无值型），只不过指针函数返回类型是某一类型的指针。

解释来源于百度百科

像。。。

typedef struct _Data{
    int a;
    int b;
}Data;//指针函数
Data* f(int a,int b){
    Data * data = new Data;
    data->a = a;
    data->b = b;
    return data;
}int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    //调用指针函数
    Data * myData = f(4,5);
    qDebug() << "f(4,5) = " << myData->a << myData->b;    return a.exec();
}

何为函数指针？

函数指针是指向函数的指针变量。 因此“函数指针”本身首先应是指针变量，只不过该指针变量指向函数。这正如用指针变量可指向整型变量、字符型、数组一样，这里是指向函数。如前所述，C在编译时，每一个函数都有一个入口地址，该入口地址就是函数指针所指向的地址。有了指向函数的指针变量后，可用该指针变量调用函数，就如同用指针变量可引用其他类型变量一样，在这些概念上是大体一致的。函数指针有两个用途：调用函数和做函数的参数。

解释来源于百度百科

那么。。。

int add(int x,int y){
    return x+y;
}
int sub(int x,int y){
    return x-y;
}
//函数指针
int (*fun)(int x,int y);int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    //第一种写法
    fun = add;
    qDebug() << "(*fun)(1,2) = " << (*fun)(1,2) ;
//第二种写法
    fun = &sub;
    qDebug() << "(*fun)(5,2) = " << (*fun)(5,3)  << fun(5,3)；    return a.exec();
}

何为二级指针

A(即B的地址)是指向指针的指针，称为二级指针，用于存放二级指针的变量称为二级指针变量．根据B的不同情况，二级指针又分为指向指针变量的指针和指向数组的指针。

解释来源于百度百科

嗯。。。

#include<stdio.h>
#include<stdlib.h>void mainA()
{
char *p[4] = { "calc","notepad","write","tasklist&pause" };
//for (int i = 0; i < 4; i++)
//{
//system(p[i]);//下标的方式访问
//}//for (int i = 0; i < 4; i++)
//{
//system(*(p+i));//下标的方式访问
//}
//轮询一个数组，需要一个指针，轮询一个指针数组，需要一个二级指针
for (int **pp = p; pp < p + 4; pp++)
{
system(*pp);
}
}void run(char*p[4])//数组没有副本机制，传递的是地址：二级指针
{
printf("run=%d\n", sizeof(p));//4
for (int **pp = p; pp < p + 4; pp++)
{
system(*pp);
}
}
void main()
{
char *p[4] = { "calc","notepad","write","tasklist&pause" };
printf("main=%d\n",sizeof(p));//16
run(p);//4
getchar();
}
//因为函数对于数组没有副本机制
//数组作为参数退化为一个指针
//指针作为参数会退化为一个二级指针

何为单向链表？

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

解释来源于百度百科

so。。。

package com.zjn.LinkAndQueue;/**
 * 自定义链表设计
 *
 * @author zjn
 *
 */
public class MyLink {
    Node head = null; // 头节点    /**
     * 链表中的节点，data代表节点的值，next是指向下一个节点的引用
     *
     * @author zjn
     *
     */
    class Node {
        Node next = null;// 节点的引用，指向下一个节点
        int data;// 节点的对象，即内容        public Node(int data) {
            this.data = data;
        }
    }    /**
     * 向链表中插入数据
     *
     * @param d
     */
    public void addNode(int d) {
        Node newNode = new Node(d);// 实例化一个节点
        if (head == null) {
            head = newNode;
            return;
        }
        Node tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = newNode;
    }    /**
     *
     * @param index:删除第index个节点
     * @return
     */
    public boolean deleteNode(int index) {
        if (index < 1 || index > length()) {
            return false;
        }
        if (index == 1) {
            head = head.next;
            return true;
        }
        int i = 1;
        Node preNode = head;
        Node curNode = preNode.next;
        while (curNode != null) {
            if (i == index) {
                preNode.next = curNode.next;
                return true;
            }
            preNode = curNode;
            curNode = curNode.next;
            i++;
        }
        return false;
    }    /**
     *
     * @return 返回节点长度
     */
    public int length() {
        int length = 0;
        Node tmp = head;
        while (tmp != null) {
            length++;
            tmp = tmp.next;
        }
        return length;
    }    /**
     * 在不知道头指针的情况下删除指定节点
     *
     * @param n
     * @return
     */
    public boolean deleteNode11(Node n) {
        if (n == null || n.next == null)
            return false;
        int tmp = n.data;
        n.data = n.next.data;
        n.next.data = tmp;
        n.next = n.next.next;
        System.out.println("删除成功！");
        return true;
    }    public void printList() {
        Node tmp = head;
        while (tmp != null) {
            System.out.println(tmp.data);
            tmp = tmp.next;
        }
    }    public static void main(String[] args) {
        MyLink list = new MyLink();
        list.addNode(5);
        list.addNode(3);
        list.addNode(1);
        list.addNode(2);
        list.addNode(55);
        list.addNode(36);
        System.out.println("linkLength:" + list.length());
        System.out.println("head.data:" + list.head.data);
        list.printList();
        list.deleteNode(4);
        System.out.println("After deleteNode(4):");
        list.printList();
    }
}