最小公倍数I

切西瓜

换位置

<pre><code>&#x27;&#x27;&#x27; 1) 1个人，不需要交换; 2) 2个人，交换一次即可，12-&gt;21; 3) 3个人以上，可以将其分成2拨人，每一拨人完全逆序过来，就可以完成圆环次序交换，即1234-&gt;2143（2次）或1234-&gt;1432（3次）; 观察发现，两拨人人数越接近，所需要的交换次数总和越小，计算到(n//2+1)个人逆序所需要的次数即可 &#x27;&#x27;&#x27; # nums[i]表示i个人完成逆序交换所需要的次数 nums = [0, 0, 1] # 则nums[i]等于第i个人与前面i-1个人每人交换一次 for i in range(3, n // 2 + 2):     nums.append(nums[i - 1] + i - 1) # 打印计算结果 print(nums[n // 2] + nums[n - n // 2])</code></pre>

与结果实际相关的是完全逆序的次数

公式推导的过程

<a href="http://www.gznb.xyz/posts/pythonTip-59-换位置/">题解： http://www.gznb.xyz/posts/pythonTip-59-换位置/</a>

将一圈人分成两半，分别逆序，操作最少def f(n):&nbsp; &nbsp; return n * (n - 1) / 2 print f(n/2) + f(n - n / 2)

简单的解法

<div style="top: 0px;">﻿﻿</div>st=[[i for i in range(n)],0] en=[n-i-1 for i in range(n)] mem=set() mem.add(tuple(st[0])) ans=0 Q=[st,] while(len(Q)!=0): &nbsp;&nbsp;&nbsp; now=Q.pop(0) &nbsp;&nbsp;&nbsp; for j in range(n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nl=now[0][:] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nl[j%n],nl[(j+1)%n]=nl[(j+1)%n],nl[j%n] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if tuple(nl) not in mem: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mem.add(tuple(nl)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Q.append([nl,now[1]+1]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if tuple(nl)==tuple(en): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans=now[1]+1 &nbsp;&nbsp;&nbsp; if ans!=0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break print(ans)&nbsp;&nbsp;&nbsp;

<div style="top: 0px;">﻿﻿</div>st=[[i for i in range(n)],0] en01=[[(n-j+1+i)%n for j in range(n)] for i in range(n)] en02=[] for t in en01: &nbsp;&nbsp;&nbsp; en02.append(tuple(t)) en=tuple(en02)&nbsp;&nbsp;&nbsp; mem=set() mem.add(tuple(st[0])) ans=0 Q=[st,] while(len(Q)!=0): &nbsp;&nbsp;&nbsp; now=Q.pop(0) &nbsp;&nbsp;&nbsp; for j in range(n): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nl=now[0][:] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nl[j%n],nl[(j+1)%n]=nl[(j+1)%n],nl[j%n] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if tuple(nl) not in mem: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mem.add(tuple(nl)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Q.append([nl,now[1]+1]) #&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; print([nl,now[1]+1]) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if tuple(nl) in en: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans=now[1]+1 &nbsp;&nbsp;&nbsp; if ans!=0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break print(ans)&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;

一个过不了的复杂解法

首先我们要找到规律人数n &nbsp; 时间t		增长规律mn		t		m1		0		none2		0		03		1		14		2		15		4		26		6		27		9		38		12		3规律出来了&nbsp;m的规律是0 0 1 1 2 2 3 3 4 4。。。 &nbsp;公式可为&nbsp; 偶数m= (n-2)/2&nbsp;基数m=(n-1)/2 t的值等于m的和 即0+1+1+2+2+3+3......公式可得偶数(m(m+1))/2 * 2 =m(m+1) &nbsp;&nbsp;奇数比偶数少加了一个m 所以奇数=偶数-当前n的m值 &nbsp; &nbsp;(m(m+1))/2 * 2 -&nbsp;m =&nbsp;m(m+1)&nbsp;- m =m*m 偶数t=m(m+1)基数&nbsp;t=m*m 把m分别带入两个公式中 偶数t=(n-2)/2 *((n-2)/2 +1)&nbsp;奇数t=(n-1)/2 *&nbsp;(n-1)/2代码如下：<pre style="padding: 9.5px; font-family: 宋体; font-size: 10.5pt; color: rgb(155, 194, 142); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; margin-top: 0px; margin-bottom: 10px; margin-left: 0px; line-height: 20px; word-break: break-all; word-wrap: break-word; white-space: pre-wrap; border-width: 1px; border-top-style: solid; border-right-style: solid; border-bottom-style: solid; border-color: rgba(0, 0, 0, 0.14902); background-color: rgb(64, 64, 64);">if n%2 == 0:
 print (n-2)/2*((n-2)/2+1)
else:
 print ((n-1)/2)*((n-1)/2)</pre>

详解

print sum([min(i,n-1-i) for i in range(1,n)])

一行~模拟下过程~~~

if n%2: &nbsp; &nbsp; print (n-1)/2+2*((n-1)/2-1+1)*((n-1)/2-1)/2 else: &nbsp; &nbsp; print (n-2)/2+((n-2)/2-1)*((n-2)/2)/2+((n-2)/2+1)*((n-2)/2)/2

没有化简 更加易懂

一行输出

if n%2: &nbsp;&nbsp;&nbsp; print (n-1)**2/4 else: &nbsp;&nbsp;&nbsp; print n*(n-2)/4

带组合数学是难！直接上结论

神秘，怎么都是数学题

&#x27;&#x27;&#x27; 1) 1个人，不需要交换; 2) 2个人，交换一次即可，12-&gt;21; 3) 3个人以上，可以将其分成2拨人，每一拨人完全逆序过来，就可以完成圆环次序交换，即1234-&gt;2143（2次）或1234-&gt;1432（3次）; 观察发现，两拨人人数越接近，所需要的交换次数总和越小，计算到(n//2+1)个人逆序所需要的次数即可 &#x27;&#x27;&#x27; # nums[i]表示i个人完成逆序交换所需要的次数 nums = [0, 0, 1] # 则nums[i]等于第i个人与前面i-1个人每人交换一次 for i in range(3, n // 2 + 2):     nums.append(nums[i - 1] + i - 1) # 打印计算结果 print(nums[n // 2] + nums[n - n // 2])

通过了

12345可以拆成123和45123-132-312-321 三步45-54 一步构成32154完成任务，共四步。可见0个数是0步, 1个数是0步， 2个数是1步， 3个数是3步，4个数是？1234-1243-1423-4123-.. 即把4移到开头需4-1步再进行123的交换就好 即f(4)=f(3)+(4-1)以此类推输出一个列表swap_ = [0,0,1,3,6,....]print(swap_(n//2)+swap_(n//2) if n%2==0 else swap_(n//2)+swap_(n//2+1))

一种我能理解的方式

123456132456312456321456321465321645321654一共6步

出题人的参考答案计算结果:人数n   时间t 增长规律mn t m1 0 none2 0 03 1 14 2 15 4 26 6 27 9 38 12 3人数前三个不用看 定死的根据示例4人 用2分钟, 四人换完最少2步,所以每换一次需要1分钟然后直到6人之前没有争议 6人的时候 要完成换位需要至少7步 所以时间不是6而是7123456一.1和6换623451二.2和3换632451三.4和5换632541四.25换635241五.35换653241六.24换653421七.34换654321无论怎么换 不重复不浪费机会最少步数都是7如果是我看不到6步换完的,还请了解的大佬将6步的过程留言发出来

我只想说出题人搞错了  难道就不能加个报错的小功能吗

首先我们要找到规律人数n &nbsp; 时间t		增长规律mn		t		m1		0		none2		0		03		1		14		2		15		4		26		6		27		9		38		12		3规律出来了&nbsp;m的规律是0 0 1 1 2 2 3 3 4 4。。。 &nbsp;公式可为&nbsp; 偶数m= (n-2)/2&nbsp;基数m=(n-1)/2 t的值等于m的和 即0+1+1+2+2+3+3......公式可得偶数(m(m+1))/2 * 2 =m(m+1) &nbsp;&nbsp;奇数比偶数少加了一个m 所以奇数=偶数-当前n的m值 &nbsp; &nbsp;(m(m+1))/2 * 2 -&nbsp;m =&nbsp;m(m+1)&nbsp;- m =m*m 偶数t=m(m+1)基数&nbsp;t=m*m 把m分别带入两个公式中 偶数t=(n-2)/2 *((n-2)/2 +1)&nbsp;奇数t=(n-1)/2 *&nbsp;(n-1)/2代码如下：<pre style="background-color:#404040;color:#9bc28e;font-family:'宋体';font-size:10.5pt;">if n%2 == 0:
 print (n-2)/2*((n-2)/2+1)
else:
 print ((n-1)/2)*((n-1)/2)</pre>

正确答案和分析

http://zhidao.baidu.com/link?url=txg5Pd6-YHfCRwJ7cFn-MpjC3MejmPV9ZO51E3gf5JlFToAVDcJ1y30-jj1JYGQX48Lgmd5BoUiYxeGZyXruy_大家轻声 深藏功与名

表示公约数都查了半天，唉不行了。

第59题：换位置

欧拉函数1

完美数II

IP判断

结尾0的个数II