C语言通过深度优先搜索来解电梯问题和N皇后问题的示例

N皇后问题
问题描述:
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上。
需求输入:
给定棋盘的大小n (n ≤ 13)
需求输出:
输出有多少种放置方法。

#include <stdio.h>
#include <math.h>

#define MAX 101

int total = 0;
char m[MAX][MAX];

int is_ok(int s,int i,int *a)
{
  int j ;
  for(j=1 ; j< s ; j++)
  if( (abs(i-a[j]) == abs(s-j)) || (i == a[j])) /*按行填入,所以只要检查列和斜列是否有皇后即可*/
    return 0 ;
  return 1 ;
}

void nfind(int s,int n,int *a)
{
  int i,p,q;

  if( s > n)
  {
    total ++ ;
    printf("========The num of %d is ========== ",total);
    for(p=1 ; p<= n ; p++)
    {
      for(q=1; q<=n ; q++)
        printf("%c ",m[p][q]);
      printf(" ");
    }

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

      if(is_ok(s,i,a))
      { 

        a[s]=i ;
        m[s][i]='O' ;
        nfind(s+1,n,a);
        m[s][i]='*' ;
      }
  }
}

int main(void)
{
  int n ,a[MAX]={0};
  scanf("%d",&n);
  memset(m,'*',sizeof(m));
  nfind(1,n,a);
  printf(" total=%d ",total);
  system("pause");
  return 0;
}

电梯问题
问题描述:
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3 3 1 2 5代表了Ki(K1=3,K2=3,……),从一楼开始。在一楼,按“上”可以到4楼,按“下”是不起作用的,因为没有-2楼。那么,从A楼到B楼至少要按几次按钮呢?
需求输入:
输入文件共有二行,第一行为三个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N),第二行为N个用空格隔开的正整数,表示Ki。
需求输出:
输出文件仅一行,即最少按键次数,若无法到达,则输出-1。
示例输入:

5 1 5
3 3 1 2 5

示例输出:

代码如下:

3

实现代码:

#include <stdio.h>
#define MAX 501

int a,b,n ;
int v[MAX],flag=0 ;

void trytofind(int x,int total)
{
   if(x-v[x] == b || x+v[x] == b)
   {

   if ( total < flag || flag == 0)
   flag = total ;

   }
   else
   {
    if(x+v[x] <= n)
    trytofind(x+v[x],total+1);
    if(x-v[x] >= 1)
    trytofind(x-v[x],total+1);
   }

}
int main(void)
{
  int i,j,k ;
  scanf("%d %d %d",&n,&a,&b);
  for(i=1 ; i<= n; i++)
  scanf("%d",&v[i]);

  trytofind(a,1) ;

  if(flag)
  printf("%d ",flag);
  else
  printf("-1 ");

  system("pause");

  return 0 ;

}
(0)

相关推荐

  • C语言使用深度优先搜索算法解决迷宫问题(堆栈)

    本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 深度优先搜索 伪代码 (Pseudocode)如下: 将起点标记为已走过并压栈; while (栈非空) { 从栈顶弹出一个点p; if (p这个点是终点) break; 否则沿右.下.左.上四个方向探索相邻的点 if (和p相邻的点有路可走,并且还没走过) 将相邻的点标记为已走过并压栈,它的前趋就是p点; } if (p点是终点) { 打印p点的坐标; while (p点有前趋) { p点 = p点的前趋;

  • 基于C语言实现的迷宫游戏代码

    本文实例讲述了基于C语言实现迷宫游戏的方法,代码备有较为详尽的注释,便于读者理解.通过该游戏代码可以很好的复习C语言的递归算法与流程控制等知识,相信对于学习游戏开发的朋友有一定的借鉴价值. 完整的实例代码如下: #include <graphics.h> #include <stdlib.h> #include <stdio.h> #include <conio.h> #include <dos.h> #define N 20/*迷宫的大小,可改

  • C语言求解最长公共子字符串问题及相关的算法分析

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子序列,并打印出最长公共子序列. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子序列. 分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的

  • C语言解决螺旋矩阵算法问题的代码示例

    赶集网校招就采用了螺旋输出矩阵作为程序题,要求将矩阵螺旋输出如: 图中6*6矩阵线条所示为输出顺序,如果输出正确的话应该输出1~36有序数字.  我想的是这么做的: #include <stdio.h> //#define LEN 1 //#define LEN 2 //#define LEN 3 #define LEN 4 void printClock(int a[][LEN]){//输出函数 int t; int i = 0, m = 0; int j = LEN, n = LEN; w

  • C语言实现的猴子分桃问题算法解决方案

    本文实例讲述了C语言实现的猴子分桃问题算法.分享给大家供大家参考,具体如下: 问题: 海滩上有一堆桃子,五只猴子来分.第一只猴子把这堆桃子凭据分为五份,多了一个,这只猴子把多的一个扔入海中,拿走了一份.第二只猴子把剩下的桃子又平均 分成五份,又多了一个,它同样把多的一个扔入海中,拿走了一份,第三.第四.第五只猴子都是这样做的,问海滩上原来最少有多少个桃子? 程序: #include<stdio.h> int divided(int n, int m) //注意该递归函数的定义 { if(n/5

  • C语言的数字游戏算法效率问题探讨实例

    最近做了这样一个题目,感觉挺有趣~题目如下: 问题描述 Winder 最近在玩一个数字游戏,该游戏是在一个n*m 的网格上进行的,每个格子上有 一个数字,代表这个格子的数值.玩家需要从网格的左上角的格子走到右下角的格子,每次 只能向右或者向下走,并且不能回头.玩家每经过一个格子可以选择分值是否加上该格子的 数值,每次游戏的初始分数都是0. Winder 想知道在每场游戏,他最多能够得到多少分值.但是,Winder 很懒,所以你必 须帮他来完成这件事. 数据输入 输入第一行两个正整数N 和M(0<

  • C语言实现图的遍历之深度优先搜索实例

    DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法.分享给大家供大家参考.具体方法如下: #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define MAX_VERTEX_NUM 10 struct Node { int adjvex; struct Node *next; int info; }; typ

  • C语言实现的猴子吃桃问题算法解决方案

    本文实例讲述了C语言实现的猴子吃桃问题.分享给大家供大家参考,具体如下: 问题: 猴子第一天摘下N个桃子,当时就吃了一半,还不过瘾,就又吃了一个.第二天又将剩下的桃子吃掉一半,又多吃了一个.以后每天都吃前一天剩下的一半零一个.到第10天在想吃的时候就剩一个桃子了,求第一天共摘下来多少个桃子? 解析: ① 从最后一天的x=1个,倒推出前一天的个数x,需要注意的是表达式为x=2(x+1),而不是x=2x+1,注意两者之间的区别,想清楚为什么第二种不正确. ② 将该表达式作为循环9次的循环体,并在该语

  • C语言使用广度优先搜索算法解决迷宫问题(队列)

    本文实例讲述了C语言使用广度优先搜索算法解决迷宫问题.分享给大家供大家参考,具体如下: 变量 head 和 tail 是队头和队尾指针, head 总是指向队头, tail 总是指向队尾的下一个元素.每个点的 predecessor 成员也是一个指针,指向它的前趋在 queue 数组中的位置.如下图所示: 广度优先是一种步步为营的策略,每次都从各个方向探索一步,将前线推进一步,图中的虚线就表示这个前线,队列中的元素总是由前线的点组成的,可见正是队列先进先出的性质使这个算法具有了广度优先的特点.广

  • 基于C语言实现简单的走迷宫游戏

    本文实例讲述了C语言实现简单的走迷宫游戏的方法,代码完整,便于读者理解. 学数据结构时用"栈"写的一个走迷宫程序,实际上用到双向队列,方便在运行完毕后输出经过的点. #include <cstdio> #include <deque> #include <windows.h> using namespace std; class node { public: int x,y; int lastOpt; }; deque<node> sta

  • C语言 数据结构中求解迷宫问题实现方法

    C语言 数据结构中求解迷宫问题实现方法 在学习数据结构栈的这一节遇到了求迷宫这个问题,拿来分享一下~ 首先求迷宫问题通常用的是"穷举求解" 即从入口出发,顺某一方向试探,若能走通,则继续往前走,否则原路返回,换另一个方向继续试探,直至走出去. 我们可以先建立一个8*8的迷宫其中最外侧为1的是墙 int mg[M+2][N+2]={ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,

  • c语言来实现贪心算法之装箱问题

    装箱问题,贪心算法求近似最优解 复制代码 代码如下: import java.util.Arrays; import java.util.Comparator; //装箱问题,贪心算法 public class Enchase {     public void test1() {         Integer[] boxs={34,6,40,2,23,12,12};         int boxCaptation=40;//箱子容量         //倒序         Arrays.

随机推荐