5

我有一个 C++ 任务，我必须用我选择的容器设计一个简单的 Knuth 问题解决方案，并研究生成的性能数据。请参阅下面的问题：

从纽约到加利福尼亚，三百万名不同的人被端对端放置。每个参与者都得到一张纸条，他在纸条上写下自己的名字和排在他西边的人的名字。队伍最西端的那个人不知道该怎么办，所以他把纸扔了；剩下的 2,999,999 张纸条被放在一个巨大的篮子里，并被带到华盛顿特区的国家档案馆。篮子里的东西被完全打乱并转移到磁带上。

此时，一位信息科学家观察到磁带上有足够的信息可以按照原始顺序重建人员列表。一位计算机科学家发现了一种方法，可以通过少于 1000 次的数据磁带进行重建，只使用磁带的顺序访问和少量的随机存取存储器。这怎么可能？

[换句话说，给定 1 ≤ i < N 的对 (xi, xi+1)，以随机顺序，其中 xi 不同，如何获得序列 x1 x2….xN，将所有操作限制为串行技术，适用于磁带上。当没有简单的方法来判断两个给定键中的哪一个在另一个之前时，这就是排序问题。

根据我的研究，我决定使用 unordered_map，而不是列表或法线贴图。我不明白的是已经提供给我们以实现为代码的幼稚解决方案：

将论文视为 (Name, Name) 元组的集合，后继者（西边邻居）和前身（东边邻居）都可以从这些元组中建立。

 - identify an individual xc
   
 - append xc to empty list
   
 - while xc has westerly neighbour

 - xc < westerly neighbour of xc

 - append xc to list

 - xc < head of list
   
 - while xc has easterly neighbour

 - xc < easterly neighbour of xc

 - prepend xc to list

我的第一个问题 - xc 只是一个随机元素，因为容器的性质无法确定顺序吗？

我的第二个问题 - 我们得到的名字在一个文件中，如下所示：

Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg

那么天真的解决方案是说我应该取名字并将其放入一个列表中，然后将姓氏放入另一个列表中吗？

抱歉，如果我完全离开，但我真的试图理解这一点！

4

2 回答 2

0

我相信解决方案是说使用一个列表。选择第一个元组，并将其名字作为列表的头部，将西风邻居作为下一项。然后，找到以西风邻居为名字的元组（当然，这是最难的部分），并从该元组中获取西风邻居并将其附加到列表中。重复，直到找不到包含最后添加的人的名字的元组。然后你知道你已经到达了西海岸。

所以，第一个 xc 本质上是随机的。之后，xc 是确定性的。说的那一行

- while xc has westerly neighbour

本质上是说“找到以当前西风邻居为自身名称的元组”。

当然，后一部分只是反过来应用相同的逻辑，以填补向东的链条。

于 2013-01-27T19:54:41.777 回答
0

第一次尝试

我这样做是为了回答，因为不可能将此作为评论。还要澄清这一点，恕我直言，至少有一半的答案

这是否意味着以下方式？

identify an individual xc
append xc to empty list
while( xc has westerly neighbour )
{
    if( xc < westerly neighbour of xc )
    {
        append xc to list
    }
    // Do not understand this:
    // - xc < head of list
}
while( while xc has easterly neighbour )
{
    if( xc < easterly neighbour of xc )
    {
        prepend xc to list
    }
}

（这只是尝试接近解决方案 - 我什至还没有考虑算法......）

第二次尝试

identify an individual xc
append xc to empty list

while( xc has westerly neighbour )
{
    xc := westerly neighbour of xc
    append xc to list
    xc := head of list

    while( xc has easterly neighbour )
    {
        xc := easterly neighbour of xc
        prepend xc to list
    }
}

看起来这是有道理的：因此，您遍历列表，尽可能收集所有西风邻居，然后对所有东风进行此操作。因此，对于通过原始列表的每次运行，排序列表变得越来越长。

第三次尝试

恕我直言，缺少一些东西：如果我解释所有可用的信息，我会得出以下解决方案。但这需要对原始磁带进行更多扫描：而不是给定的 10.000 次，而是扫描大约 750.000 次。有任何想法吗？

#include <vector>
#include <algorithm>
#include <iostream>
#include <list>

size_t constexpr max_men { 3000000 };

typedef std::tuple< int, int > neighbors_t;
typedef std::vector< neighbors_t > pool_t;

int main() {

  // Need a vector here for random_shuffle - but using it further down
  // just with sequencial methods.
  pool_t pool_list;
  for( size_t i { 0 }; i < max_men - 1; ++i ) {
    pool_list.push_back( std::make_tuple( i, i + 1) );
  }
  std::random_shuffle( pool_list.begin(), pool_list.end() );


  // Use the algorithm to get it sorted again

  // identify an individual xc:
  // Pick first from first tuple
  // append xc to empty list
  std::list<int> sorted_list;
  sorted_list.push_back( std::get<0>( pool_list.front() ) );

  // Count the number of tape scans
  size_t tape_scans { 0 };

  do {
    // Scan through the pool_list
    for( neighbors_t n : pool_list ) {

#if 0
      std::cout << "n [" << std::get<0>( n ) 
        << "] sorted_list [";
      for( int i : sorted_list ) {
        std::cout << i << " ";
      }
      std::cout << "]" << std::endl;
#endif

      // while( xc has westerly neighbour )
      // Found westerly neighbour
      if( std::get< 1 >( n ) == sorted_list.front() ) {
        // append xc to list
        sorted_list.push_front( std::get< 0 >( n ) );
      }
      if( std::get< 0 >( n ) == sorted_list.back() ) {
        // append xc to list
        sorted_list.push_back( std::get< 1 >( n ) );
      }
    } 
    ++tape_scans;
    std::cout << "Tape Scans needed [" << tape_scans 
          << "] sorted list size [" << sorted_list.size() << "]"
          << std::endl;
  } while( sorted_list.size() < max_men );

  std::cout << "Tape Scans needed [" << tape_scans << "]" << std::endl;

  return 0;
}
于 2013-01-27T19:57:30.430 回答