狐狸逮兔子问题

问题描述

围绕着山顶有 20 个圆形排列的洞，狐狸要吃兔子，兔子说：“你可以吃我，但必须先找到我，我就藏在这 20 个洞中，你先到1号洞找，第二次隔 1 个洞（即 3 号洞）找，第三次隔 2 个洞（即 6 号洞）找，以后如此类推，次数不限”。但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问：兔子究竟藏在哪个洞里?

解决方案

典型的数据结构 – 线性表的应用，可以采用数组不断取余模拟循环遍历来实现，也可以直接用循环链表来实现。

顺序表（数组）实现

用数组来存储，以取余的方式模拟循环

#include<iostream>

using namespace std;

const int wholeNum = 20;
const int findNum = 10000;

int main()
{
  bool whole[wholeNum] = { 0 };
  for (int i = 2, j = 0; i < findNum + 2; i++)
  {
    if (!whole[j])
    {
      whole[j] = 1;
    }
    j += i;
    j %= wholeNum;
  }

  for (int i = 0; i < wholeNum; i++)
  {
    if (!whole[i])
    {
      cout << i + 1 << endl;
    }
  }

  return 0;
}

循环链表实现

直接用循环链表来模拟

#include <iostream>

using namespace std;

const int wholeNum = 10;
const int findNum = 1000;

struct Node
{
  bool flag;
  Node* next;
};

Node* CreatList(bool flag);
Node* AddFront(Node* l, bool flag);

int main()
{
  Node* head = CreatList(false);
  for (int i = 1; i < wholeNum; i++)
  {
    AddFront(head, false);
  }
  // 循环链表
  Node* p = head;
  for (int i = 2; i < findNum + 2; i++)
  {
    if (!p->flag)
    {
      p->flag = true;
    }
    for (int j = 0; j < i; j++)
    {
      p = p->next;
    }
  }

  p = head;
  int i = 1;
  do
  {
    if (!p->flag)
    {
      cout << i << endl;
    }
    i++;
    p = p->next;
  } while (p != head);

  return 0;
}

// 使用循环链表
Node* CreatList(bool flag)
{
  Node* p = (Node*)malloc(sizeof(Node));
  p->flag = flag;
  p->next = p;
  return p;
}

Node* AddFront(Node* l, bool flag)
{
  Node* p = (Node*)malloc(sizeof(Node));
  p->flag = flag;
  p->next = l->next;
  l->next = p;
  return l;
}

DONE！