初探Swift,Swift变量声明,let和var分别声明常量和变量。Swift数据类型,包括整型,浮点型,字符型,布尔型,可选型等,已经强制类型转换和if选择。

//-----------变量相关----------

//常量

let maxNum = 1000

//变量

var index = 0


var a=0.0, y=0, z=0

a = 1;

a = 1.1;

//报错

//a = "a";


//显示申明类型

var test : Int

test = 10


var red, green, blue : Int

//十进制

red = 17;

//二进制,以0b开头

red =0b10001

//八进制,以0o开头

red = 0o21

//十六进制,以0x开头

red = 0x11


//科学计数法

let b = 0.012

letc =1.2e-2


//多位整数的表示法

lete =1000000

letf =1_000_000

letg =1_000_000


//自动类型转换

let h:Float = 1

//Xcode beta2会将1.2转为1,而Xcode beta3直接报错。

//let i:Int = 1.2


//强制类型转换

let j:Double = Double(h) + b


//变量名,任何unicode都可以

let 姓名 = "小明"

println(姓名 + "你好")




//----------选择-----------

let bool1 = true

let bool2:Bool = false


//即使语句块只有一行,花括号{}也不能省略,在选择里,只有truefalse10都是不可以的。

if bool1{

    println("hello");

}else if bool2{

    println("world");

}else{

    println("swift");

}




//---------元组-----------

let tuples_1 = ("小明", "", 21, true)

//元组可以赋值给变量

let (name, sex, age, status) = tuples_1

println("姓名:"+name+",性别:"+sex);

//元祖可以用.0.1.2来访问

println("姓名:"+tuples_1.0+",性别:"+tuples_1.1);


//每个元祖都赋一个key

let tuples_2 = (date:"2015-01-05", time:"16:06", author:"lane")

println("日期:"+tuples_2.date+" "+tuples_2.time+",作者:"+tuples_2.author);

println("日期:"+tuples_2.0+" "+tuples_2.1+",作者:"+tuples_2.2);


//至提取元组的第一个值,不关心后面的值

let login = (true, "小明")

let (staic, _) = login

if staic{

    println("hi");

}else{

    println("hi hi");

}

//元组的类型显示声明

let login2:(Bool, String) = (true, "小明")



//可选型optional

var optionalVar1:Int?

optionalVar1=1


let userAge = "18"

var age = userAge.toInt()


if(age != nil){

    println("You age is " + String(age!) )

}else{

   println("Invalidate userInput")

}


//解包

if let userInput = userAge.toInt(){

    println("you age is\(userInput)");

}

let m:String? = "hello";

let n:String! = "hi";

    Dijkstra算法是指定一个源点,求得这个源点到各个点的最短路径。Dijkstra算法通过不断的松弛边,每次更新相邻点的路径,使之两点之间的距离成为最短的路径。Dijkstra算法缺点是不能有负权边的值。

    松弛边:点A到点B的距离是10,点A到点C的距离是15,点B到点C的距离是3,那么点A到点C的最短距离就是13。此时15这个值将会被废弃,永不使用,以后谈论点A到点C的距离都是直接说13。这就是松弛边。

    现在有如下图,6个点,9条边,边是有方向的哦。


无标题.jpg


    Dijkstra算法的步骤,假设源点为点(1):

    1、先求得源点到各个点的距离。则数组为dis['1'=>0, '2'=>1, '3'=>12, '4'=>'∞', '5'=>'∞', '6'=>'∞'];并且用数组e[i][j]表示点i到点j的距离。

    2、将各个点分为2个部分,P部分是已知的点1到该点距离为最短路径的点的集合,此时P部分只有点1到点1的距离为0是已知的,点1到点2,点1到点3的距离是不是最短路径暂时不可是,所以他们不属于这部分。Q部分是未知的点1到该点距离为最短路径的点的集合。

    3、在集合Q中选择一个点,这个点距离源点(1)号点最近,即步骤一得出的dis数组中该key所对应的值最小,此时这个点为2号点,因为dis[2]最小,为1。则点1到点2的距离dis[2]是最短的路径,已经已知了,所以将(2)号点加入到集合P中。此时以(2)好点为源点,对所有的边松弛一次,看看有没有一个点X,可以使得点1到点2再到点X的距离小于点1到点X的距离,如果有,则点1到点X的最短路径就是点1到点2再到点X的值。即如果dis[3] > dis[2] + e[2][x],则dis[3] = dis[2] + e[2][x]。

    4、重复第三步,知道集合Q为空。


Dijkstra算法的代码如下:

#include <stdio.h>

int main(){

    int startPoint = 1;

    int limitValue = 999;

    int e[10][10], dis[10], book[10], i, j, m, n, point1, point2, length, u, v, min;

   //n是点数,m是边数

    scanf("%d %d", &n, &m);

   //如果i=j,就是自己到自己的距离,那么就是0,否则,就初始化非正无穷

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            if(i==j)

                e[i][j] = 0;

            else

                e[i][j] = limitValue;

        }

    }

   //边的长度,即点到点的距离

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &point1, &point2, &length);

        e[point1][point2] = length;

    }

   //初始化源点到各点的距离的数组,我们的源点为1

    for(i=1; i<=n; i++){

        dis[i] = e[startPoint][i];

    }

   //book数组用来标记那个点是已经走过了的。

    for(i=1; i<=n; i++){

        book[i] = 0;

    }

   //从源点开始

    book[startPoint] = 1;

   //以下就是Dijkstra算法的重点,是核心思想

    for(i=1; i<=n-1; i++){

       //找到离远点最近的点

        min = limitValue;

        for(j=1; j<=n; j++){

            if(book[j] == 0 && dis[j] < min){

                min = dis[j];

                u = j;

            }

        }

        book[u] = 1;

        for(v=1; v<=n; v++){

           //如果小于limitValue,则证明点u到点v是有路走的

            if(e[u][v] < limitValue){

                if(dis[v] > dis[u] + e[u][v]){

                    dis[v] = dis[u] + e[u][v];

                }

            }

        }

    }

    //输出

    for(i=0; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}


输入:

6 9

1 2 1

1 3 12

2 3 9

2 4 3

3 5 5

4 3 4

4 5 13

4 6 15

5 6 4

输出

0 1 8 4 13 17

这个输出便是点1到各个点的最短距离。


Ps:本算法参考《啊哈!算法》一书。

   任意两点最短路径被称为多源最短路径,即给定任意两个点,一个出发点,一个到达点,求这两个点的之间的最短路径,就是任意两点最短路径问题,多源最短路径,而Floyd-Warshall算法最简单,只有5行代码,即可解决这个问题。

    比如三个城市,城市1,城市2,城市3。从城市1到城市3需要10公里,从城市1到城市2需要3公里,从城市2到城市3需要4公里,如下图:

4F966EED-1AD1-4FD9-ABB4-0448137A13E4.png


那么从城市1到城市3,如何走更近?1到3是直达,但是却10公里,而1到2到3,虽然转一下,但是距离短了,只要7公里。

这就引出了我们的观念,一个点到另一个点要变短,就要引入第三个点,甚至第四个点,第五个点。


假设在map数组里存储了点i到点j的距离map[i][j],那么我们引入第三个点k,则如果点i到点j的距离比点i到点k加点k到点j,则点i到点j的最短距离是点i到点k加点k到点j。

即如果map[i][j]<map[i][k]+map[k][j],则map[i][j]=map[i][k]+map[k][j]


这就是Floyd-Warshall算法。核心代码如下:

//只能从k中转

    for(k=1; k<=cityCount; k++){

        //从i出发

        for(i=1; i<=cityCount; i++){

            //到j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

三个for循环,加一个if,加一个赋值,简简单单的五行代码,就实现了任意一个点到任意另一个点的最短距离。

显而易见,时间复杂度是O(n3).


完整代码如下

#include <stdio.h>

int map[11][11] = {{0}};

int book[11] = {0};

int main(){

    int i, j, k, cityCount, roadCount, length, x, y;

    scanf("%d %d", &cityCount, &roadCount);

    for(i=1; i<=cityCount; i++){

        for(j=1; j<=cityCount; j++){

            map[i][j] = 0;

        }

    }

    for(i=1; i<=roadCount; i++){

        scanf("%d %d %d", &x, &y, &length);

        map[x][y] = length;

    }

   //只能从k中转

    for(k=1; k<=cityCount; k++){

        //i出发

        for(i=1; i<=cityCount; i++){

            //j结束

            for(j=1; j<=cityCount; j++){

                if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue;

                if(map[i][j] > (map[i][k] + map[k][j])){

                    map[i][j] = map[i][k]+ map[k][j];

                }

            }

        }

    }

   //现在的map里就是从一个点i到另一个点j的最短距离map[i][j]

    printf("点1到点5的最短路径是:%d", map[1][5]);

}


输入

5 8

1 2 3

1 3 2

1 5 10

2 3 1

3 5 3

3 4 5

4 5 1

2 4 8


输入,5

图的遍历,我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举!

如下的图:

F1062065-133F-4EB8-AD78-3E7168FF00C7.png

点1和点2,3,5有边,点3和点5有边,点2和点4有边。mac画的好累。。没有鼠标。。


输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。

        5 5

        1 2

        1 3

        1 5

        2 4

        3 5


深度优先搜索来遍历图,代码如下:

#include <stdio.h>

int a[101][101];

int book[101];

int m, n, sum=0;

void dfs(int node);

int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

    dfs(1);

}

void dfs(int node){

    printf("%d ", node);

    sum++;

    if(sum == n){

        return;

    }

    int i = 0;

    for(i=1; i<=n; i++){

        if(book[i] != 0 || a[node][i] != 1) continue;

        book[i] = 1;

        dfs(i);

    }

}

输出:1,2,4,3,5



广度优先搜索来遍历图,代码如下:

输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。


#include <stdio.h>

int a[101][101];

int book[101];

int m, n;

void dfs(int node);


int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

   //广度优先搜索

    int head = 0, tail = 0;

    int queue[25];

    for(i=0; i<25; i++) queue[i] = 0;

    queue[tail] = 1;

    tail++;

    while(head<tail){

        printf("%d ", queue[head]);

        for(i=1; i<=n; i++){

            if(book[i] != 0 || a[queue[head]][i] != 1) continue;

            book[i] = 1;

            queue[tail] = i;

            tail++;

        }

        head++;

    }

}

输出:1,2,3,5,4

    上一章我们编写了一个小游戏:炸弹人游戏。使用广度优先搜索解决的,本章将用深度优先搜索来解决。

关于广度优先搜索解决炸弹人游戏和炸弹人游戏的描述》点击查看

什么是深度优先搜索》点击查看    


深度优先搜索的核心代码如下:说白了,就是一条路走到黑,然后回头倒着走看看有没有别的岔路口,不断递归。

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}


深度优先搜索实现炸弹人游戏的完整代码如下:

#include<stdio.h>

char a[20][20];

int book[20][20], max, mx, my, n, m;

//获取点(i, j)可以炸死多少敌人。

int getnum(int i, int j);

//深度优先搜索,对点(x, y)进行深度优先搜索

void dfs(int x, int y);

void main(){

    int i, startx, starty;

    //地图长n,宽m,起始位置坐标为startx,starty

    scanf("%d %d %d %d", &n, &m, &startx, &starty);

    for(i=0; i<n; i++){

        printf("Line : %d", i);

        scanf("%s", a[i]);

    }

    book[startx][starty] = 1;

    max = getnum(startx, starty);

    mx = startx;

    my = starty;

    dfs(startx, starty);

    printf("炸弹放在%d,%d的位置,可以炸死%d人", mx, my, max);

}


int getnum(int i, int j){

    int x, y, sum=0;

    //统计点(i, j)的左边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x--;

    }

    //统计点(i, j)的右边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        x++;

    }

    //统计点(i, j)的上边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y--;

    }

    //统计点(i, j)的下边可以消灭多少敌人

    x = i;

    y = j;

    //如果是墙就停止

    while(a[x][y] != '#'){

        if(a[x][y] == 'G') sum++;

        y++;

    }

    return sum;

}

void dfs(int x, int y){

    int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    int k, sum, tx, ty;

    sum = getnum(x, y);

    if(sum > max){

        max = sum;

        mx = x;

        my = y;

    }

    for(k=0; k<4; k++){

        tx = x + next[k][0];

        ty = y + next[k][1];

        //判断边界

        if(tx<0 || tx > n-1 || ty < 0 || ty > n-1) continue;

        //判断墙和是否走过

        if(a[tx][ty] != '.' || book[tx][ty] != 0) continue;

        book[tx][ty] = 1;

        dfs(tx, ty);

    }

    return;

}


输入:第一次要求输入地图的长、宽、起始X坐标、起始Y坐标:13 13 3 3


第二次要求输入的就是地图了,每次一行,如下:

#############

#GG.GGG#GGG.#

###.#G#G#G#G#

#.......#..G#

#G#.###.#G#G#

#GG.GGG.#.GG#

#G#.#G#.#.#.#

##G...G.....#

#G#.#G###.#G#

#...G#GGG.GG#

#G#.#G#G#.#G#

#GG.GGG#G.GG#

#############


输出:炸弹放在7,11的位置,可以炸死10人.


Ps:代码案例来源于《啊哈!算法》一书