当前位置：首页 > news >正文

UVa 371 Ackermann Functions

news 2026/6/13 15:20:04

题目描述

阿克曼函数的一个特性是：函数生成的数列长度无法直接从输入值计算得出。一种特定的整数阿克曼函数定义如下：

f(n)={n/2if n is even3n+1if n is odd f(n) = \begin{cases} n/2 & \text{if } n \text{ is even} \\ 3n + 1 & \text{if } n \text{ is odd} \end{cases}f(n)={n/23n+1ifnis evenifnis odd

该阿克曼函数的特性是它最终收敛到111。示例（起始值在方括号中，后跟生成的数列，数列长度在大括号中）：

[10] 5 16 8 4 2 1 {6}[10]\ 5\ 16\ 8\ 4\ 2\ 1\ \{6\}[10]5168421{6}
[13] 40 20 10 5 16 8 4 2 1 {9}[13]\ 40\ 20\ 10\ 5\ 16\ 8\ 4\ 2\ 1\ \{9\}[13]4020105168421{9}
[14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}[14]\ 7\ 22\ 11\ 34\ 17\ 52\ 26\ 13\ 40\ 20\ 10\ 5\ 16\ 8\ 4\ 2\ 1\ \{17\}[14]7221134175226134020105168421{17}
[19] 58 29 88 44 22 … 2 1 {20}[19]\ 58\ 29\ 88\ 44\ 22\ \dots\ 2\ 1\ \{20\}[19]5829884422…21{20}
[32] 16 8 4 2 1 {5}[32]\ 16\ 8\ 4\ 2\ 1\ \{5\}[32]168421{5}
[1] 4 2 1 {3}[1]\ 4\ 2\ 1\ \{3\}[1]421{3}

输入格式

输入包含多行，每行两个整数，表示区间的起始和结束值。最后一行以0 0结束。

输出格式

对于每个区间，输出：

Between L and H, V generates the longest sequence of S values.

其中LLL和HHH是区间的边界（小的在前），VVV是生成最长序列的第一个值（如有并列取较小的），SSS是序列长度。

样例输入

1 20 35 55 0 0

样例输出

Between 1 and 20, 18 generates the longest sequence of 20 values. Between 35 and 55, 54 generates the longest sequence of 112 values.

题目分析

问题的本质

这是经典的3n+13n+13n+1问题（也称考拉兹猜想、冰雹猜想）。需要计算区间内每个数生成到111的序列长度，并找出最长者。

序列长度定义

从起始数开始，按规则生成，直到到达111为止。注意：起始数本身也算一个值。

例如：[10]→5→16→8→4→2→1[10] \to 5 \to 16 \to 8 \to 4 \to 2 \to 1[10]→5→16→8→4→2→1，长度为666（101010到111共666个数）。

数据范围

输入值在323232位整数范围内，但中间值可能超过323232位，需要使用long long。

优化策略

使用记忆化搜索（memoization\texttt{memoization}memoization）缓存已计算的值。由于区间最大可能很大（如1∼1061 \sim 10^61∼106），直接计算每个数会重复大量计算。

参考代码

// Ackermann Functions// UVa ID: 371// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intcache[500010]={0};// 缓存序列长度// 递归计算从 number 到 1 的序列长度intcounter(longlongintnumber){// 奇数：3n+1，偶数：n/2if(number&1)number+=(number<<1)+1;elsenumber>>=1;if(number==1)return1;// 如果在缓存范围内且未计算过，递归计算if(number<=500000){if(!cache[number])cache[number]=counter(number);return1+cache[number];}// 超出缓存范围，继续递归return1+counter(number);}intmain(){ios::sync_with_stdio(false);// 预处理所有 1..500000 的序列长度for(inti=1;i<=500000;i++)cache[i]=counter(i);intfirst,second,start,end;while(cin>>first>>second,first&&second){start=min(first,second);end=max(first,second);intresult=0,maxi=start;for(inti=start;i<=end;i++){longlongtemp=i;intsteps=0;// 处理大于缓存范围的值，直到进入缓存范围while(temp>500000){if(temp&1)temp+=(temp<<1)+1;// 3*temp+1elsetemp>>=1;// temp/2steps++;}// 加上缓存中的长度steps+=cache[temp];// 更新最大值if(steps>result){result=steps;maxi=i;}}cout<<"Between "<<start<<" and "<<end;cout<<", "<<maxi<<" generates the longest sequence of "<<result<<" values."<<endl;}return0;}