php - 使用PHP分配房间的算法

Question

我需要有关将房间分配给人们的算法的帮助。我需要重新整理房间列表以将房间分配给一个人，并且在将第四个人分配给房间后，它应该不在列表中（应该不可用）。我还没有通过PHP改组和排序功能获得任何运气。

任何帮助（指针，参考等）将不胜感激。

Answer 1

这听起来既是一项家庭作业，又是成千上万个解决方案的问题。

正如Jack所说的那样，请先尝试开发算法，然后再尝试在代码中实现它。如果您在理解时遇到困难，那就想象一下场景并尝试编写简单的规则来解决现实生活中的问题

假设我有一个有10个房间的走廊。每个房间最多可容纳4人。然后，有35个人出现并希望分配到房间。我该怎么做？

我可能会从走廊的开头开始，填满第一个房间，然后填满下一个房间，然后继续直到我用完人或房间（以先到者为准）。该解决方案的优点是不必走得很远，而将4人挤到一个房间而不是均匀地分散。

如果您选择将它们均匀地散布，则需要在第一个房间放一个，然后在第二个房间放一个，依此类推。直到您用完所有房间，然后再回到每个房间放第二个人。

由于您有两种方法可以执行此操作，因此下一步是确定如何在代码中表示基本组件。您需要一种代表房间的方式和一种代表人的方式。房间的最重要特征是最多可容纳四个人，但始终必须知道要容纳多少人。因此，最好将每个房间都视为自己的房间号，这个数字告诉您房间中已经有多少人了。

在PHP中，如果要关联和排序的多个数字（就像走廊中的房间一样），可以使用数组。当您有多个需要彼此关联并保持其各自顺序的ANY变量时，这是正确的。

$rooms = array(0, 0, 0, 0, 0); // 5 rooms, all with 0 people in them

如果您的房间需要知道谁留在房间里（如果他们需要区分不同的客人），那么您可以将每个房间视为由4个元素组成的数组，其中每个元素代表一个人并能够识别该人。

$rooms = array(
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null),
    array(null, null, null, null)
);

创建房间后，将有一定数量的人在等待进入房间。由于每个人仅算作 1，除非您需要记住每个人的其他信息（例如他们的姓名，年龄等），否则您应该能够看到一种非常方便的代表人的方式。

$peopleNotInARoomYet = 10;

如果您确实需要记住有关这些人的其他信息（假设分配房间后，系统提示您“鲍勃在哪个房间里？”的问题），那么您将需要一些更聪明的东西。也许是一系列班级，每个班级代表一个人。当然，除非该人仅需要由单个变量表示。然后，您可以将他们煮成一个数组。

$peopleNotInARoomYet = array("Bob", "Sally", "Bill", "Mary");
//or
$peopleNotInARoomYet = array(new Person('Bob'), new Person('Sally'), new Person('Bill'), new Person('Mary'));

请注意，第二种方法要求已经定义了 Person类，如果不小心，它可能会非常复杂。

一旦有了代表人们的方式，就想遍历每个人来找到他们的房间。如果人用一个数字表示，则如下所示：

while($peopleNotInARoomYet > 0){
    // Assign a room
    $peopleNotInARoomYet--;
}

如果人员表示为数组，则可能需要考虑使用PHP array_pop()函数。

PHP.net array_pop manual

$nextPerson = array_pop($peopleNotInARoomYet){
while($nextPerson != NULL){
    // Assign a room
    $nextPerson = array_pop($peopleNotInARoomYet);
}

现在有了一种表示房间和人的方式，您的新任务是从上面接受我们对分配的定义，并将其转换为代码。因此，让我们看一下我们的第一个（也许更简单）的方法。我们将人们放到一个房间，直到房间满为止，然后转到下一个房间。

这实际上带来了一些算法挑战。首先，您如何“将某人带入房间”？

答案实际上取决于我们使用的房间定义。如果我们只是有一个整数数组（当我们关心一个房间中有多少人，却不在乎谁在房间中时），那么我们需要向这个整数加一个。

如果我们有一个由4个元素组成的数组，那么我们需要找到第一个空元素并将人放置在该元素中。将一个人放到非空元素中将替换以前在那里的人。

由于从第一次尝试将规则集转换为代码很明显，该方法将根据所选择的实现而有所不同，在本示例的其余部分中，我将假设房间只需要知道其中有多少人，而不是谁是谁。在他们具体。如果您确实需要这些进一步的信息，那么这是一个由读者自己决定的课程。

因此，这是我们对房间，人的定义以及循环的开始：

<?php
    $rooms = array(0, 0, 0, 0, 0); // 5 empty rooms
    $peopleNotInRoomsYet = 14; // We'll choose a number that won't divide evenly

    while($peopleNotInRoomsYet > 0){
        // Assign a room
        $peopleNotInRoomsYet --;
    }
?>

而且我们知道，一旦我们选择要放置某人的房间，实际上将他们放置在其中涉及以下内容：

$rooms[$roomNumber]++;

现在，让我们回到我们最初的问题定义，看看我们从哪里开始。我们要填充第一个房间，然后填充第二个，然后填充第三个，依此类推。

因此，首先我们需要一种定义填充房间的方法。填满一个房间要涉及将人们放入其中（完成），直到它填满（没有完成）。因此，现在我们需要一种检查房间是否已满的方法。

if($rooms[$roomNumber] == 4)

应该做得很好。因此，现在我们有了一种“将房间填满直到填满”的方法。但是在此之后，我们需要从下一个房间开始。这意味着我们需要始终知道我们当前正在填充哪个房间。如果我们需要了解一些新内容，则需要一个新变量。我们将此变量称为 $roomNumber。我们将从 $roomNumber = 0;（数组中的第一个房间）开始，一直到 5。由于没有第六个房间（元素5），因此如果 $roomNumber变为5，我们的人太多了。

<?php
    $rooms = array(0, 0, 0, 0, 0); // 5 empty rooms
    $peopleNotInRoomsYet = 14; // We'll choose a number that won't divide evenly
    $roomNumber = 0;

    while($peopleNotInRoomsYet > 0){ // If there are people waiting...
        if($rooms[$roomNumber] == 4){ // If the room is full...
            $roomNumber ++; // Go to the next room
        }
        if($roomNumber == 5){ // If we are out of rooms...
            die("Too many people!!!"); // die
        }
        $rooms[$roomNumber] ++; // Otherwise, add someone to the room
        $peopleNotInRoomsYet --; // And remove them from the waiting list
    }
?>

我知道对于最后的少量代码来说，这是很长的时间，但是我试图解释从概念到代码的过程。认识到需要遵循的简单规则，然后认识到需要跟踪的项目。还要记住，我发布的解决方案仅在最简单的情况下起作用，因为您不需要知道房间里的人是多少。它还假定没有任何房间以任何人开始。如果第二个房间开始满了，那么该算法将崩溃，因为我没有检查。读者还有很多修改要做，但这应该使您指向正确的方向。