数学中国

标题: 至少进行几次相邻两数位置互换，才能将 {1,2,…,100} 变成 {2,4,…,100,99,97,…,1}？ [打印本页]

作者: dodonaomikiki 时间: 2022-12-10 01:29
标题: 至少进行几次相邻两数位置互换，才能将 {1,2,…,100} 变成 {2,4,…,100,99,97,…,1}？
2022THU大中衔接测试题，应该比较趣味

题目：

至少进行多少次相邻两数位置互换的操作，

才能将\(｛1,2, 3 ... ....98，99，100｝\)变为\(｛2, 4 ... ....100， 99， 97 ， ... ....1｝？\)

作者: dodonaomikiki 时间: 2022-12-10 01:38
本帖最后由 dodonaomikiki 于 2022-12-10 01:47 编辑

wode计算，仅供参考，不晓得对不

\(          1+3+5+7+9+ ... ....(1+2*49)    \)
\(          =\frac{(1+99)50}{2}    \)
\(          =2500             \)

作者: 王守恩 时间: 2022-12-10 16:50
{1,2} 变成 {2,1}需要进行 1 次。
{1,2,3} 变成 {2,3,1}需要进行 2 次。
{1,2,3,4} 变成 {2,4,3,1}需要进行 4 次。
{1,2,3,4,5} 变成 {2,4,5,3,1}需要进行 6 次。
{1,2,3,4,5,6} 变成 {2,4,6,5,3,1}需要进行 9 次。
{1,2,3,4,5,6,7} 变成 {2,4,6,7,5,3,1}需要进行 12 次。
{1,2,3,4,5,6,7,8} 变成 {2,4,6,8,7,5,3,1}需要进行 16 次。
{1,2,3,4,5,6,7,8,9} 变成 {2,4,6,8,9,7,5,3,1}需要进行 20 次。

作者: dodonaomikiki 时间: 2022-12-10 18:27
王老师
1
2
4
6
9
12
16
20

这是一个什么样规律的数列呢？

作者: 王守恩 时间: 2022-12-10 18:52

dodonaomikiki 发表于 2022-12-10 18:27
王老师
1
2

{1,2} 变成 {2,1}需要进行 1 次。

{1,2,3,4} 变成 {2,4,3,1}需要进行 4 次。

{1,2,3,4,5,6} 变成 {2,4,6,5,3,1}需要进行 9 次。

{1,2,3,4,5,6,7,8} 变成 {2,4,6,8,7,5,3,1}需要进行 16 次。

{1,2,3,4,5,6,7,8,9,10} 变成 {2,4,6,8,10,9,7,5,3,1}需要进行 25 次。

作者: dodonaomikiki 时间: 2022-12-10 19:16

王守恩发表于 2022-12-10 18:52
{1,2} 变成 {2,1}需要进行 1 次。

{1,2,3,4} 变成 {2,4,3,1}需要进行 4 次。

我的想法：

这样【从头】开始，进行数字互换，会不会很不划算？会不会很辛苦‘’用很多时间？

能不能【从尾巴】开始~~~因为尾巴开始的话，
我感觉比较划算，
计算简洁，
迅即出答案

如果我木有算错，感觉尾巴开始，比较省力，很快能搞出答案

作者: 王守恩 时间: 2022-12-11 06:37

dodonaomikiki 发表于 2022-12-10 19:16
我的想法：

嗨！我也是【从尾巴】开始的呀！

{1,2} 变成 {2,1}需要进行 1 次。
移动: 1-1次。

{1,2,3,4} 变成 {2,4,3,1}需要进行 4 次。
移动: 1-3次, 3-1次。

{1,2,3,4,5,6} 变成 {2,4,6,5,3,1}需要进行 9 次。
移动: 1-5次, 3-3次, 5-1次。

{1,2,3,4,5,6,7,8} 变成 {2,4,6,8,7,5,3,1}需要进行 16 次。
移动: 1-7次, 3-5次, 5-3次, 7-1次。

{1,2,3,4,5,6,7,8,9,10} 变成 {2,4,6,8,10,9,7,5,3,1}需要进行 25 次。
移动: 1-9次, 3-7次, 5-5次, 7-3次, 9-1次。

作者: dodonaomikiki 时间: 2022-12-11 06:53

好吧，俺还得再好好想一想~~~
可能题目有难度！

我那样算，变成一道初中题啦！
青瓦大学应该不会出比较低智商的题目

作者: 王守恩 时间: 2022-12-11 07:52

dodonaomikiki 发表于 2022-12-11 06:53
好吧，俺还得再好好想一想~~~
可能题目有难度！

直接在大数不容易算，间接在小数容易算，目的很明确：要在小数里找出规律来。

做一道题，我们要有收获。谢谢 dodonaomikiki ！这是一道好题，让我们思维发散。

至少进行几次相邻两数位置互换，才能将 {1,2,3,4,…} 变成 {一堆乱七八糟的数}

至少进行几次相邻两数位置互换，才能将{一堆乱七八糟的数} 变成 {1,2,3,4,…}

至少进行几次相邻两数位置互换，才能将 {一堆乱七八糟的数} 变成 {一堆乱七八糟的数}

作者: 王守恩 时间: 2022-12-11 13:10
做一道题，我们要有收获。谢谢 dodonaomikiki ！这是一道好题，让我们思维发散。

至少进行几次相邻两数位置互换，才能将 {1,2,3,4,…} 变成 {一堆乱七八糟的数}
譬如：{1,2,3,4,5,6,7,8,9} 变成 {3,9,2,7,4,8,1,6,5}

至少进行几次相邻两数位置互换，才能将{一堆乱七八糟的数} 变成 {1,2,3,4,…}
譬如：{8,7,9,4,3,6,2,1,5} 变成 {1,2,3,4,5,6,7,8,9}

至少进行几次相邻两数位置互换，才能将 {一堆乱七八糟的数} 变成 {一堆乱七八糟的数}
譬如：{5,1,9,6,3,7,2,4,8} 变成 {4,7,8,6,2,3,1,5,9}

最多进行几次相邻两数位置互换，可以将 {一堆乱七八糟的数} 变成 {一堆乱七八糟的数}

作者: lihp2020 时间: 2022-12-12 10:57
读题  看两个数列的规律
把 1~n的的顺序序列  A 转换成前偶后齐  (偶数从小到大奇数从大到小)  B

至少分析
理论上其实有个最少值  其实就是让每一次移动都是有效的移动  不要产生垃圾移动  那就是最小值
(可能是我这句有点解释不清)
大学学过一个名词叫逆序数可以自行百度看看
好像就是求逆序数？？
A相对B求逆序数还是有点恶心
可以相对B求A的逆序数

(A转换成B)的最少次数肯定=(B转换成A)的最少次数

先来个简单的
2 4 6 8 10 9 7 5 3 1

0+...+0+ 1+3+..+ (n-1)

其实结果很明显出来了

如果n是偶数
((n-1 +1 )* n/2 )/2
如果是奇数
((n-1 + 2)*(n-1)/2)/2

作者: lihp2020 时间: 2022-12-12 11:05
至少进行几次相邻两数位置互换，才能将 {一堆乱七八糟的数} 变成 {一堆乱七八糟的数}
譬如：{5,1,9,6,3,7,2,4,8} 变成 {4,7,8,6,2,3,1,5,9}

这个  我们进行转换  我们就认为4<7<8<6<2<3<1<5<9
就好了但是能识数的认为很难理解
那么我们借助第三方数字字母排序
计算 4=a 7=b

{h,g,i,d,f,b,e,a,c} 变成 {a,b,c,d,e,f,g,h,i}

abcd  字母表熟悉可以再
计 a=1 b=2 转换一下
{8,7,9,4,6,2,5,1,3} 变成 {a,b,c,d,e,f,g,h,i}

   {8,7,9,4,6,2,5,1,3}
逆序数= 0+1+0+3+3+5+4+7+6=29

也就是 29次可以把 {5,1,9,6,3,7,2,4,8} 变成 {4,7,8,6,2,3,1,5,9}

作者: lihp2020 时间: 2022-12-12 11:06
大中衔接测试题一般会用到一个大学中很明显的知识而再大学一下很少学习的知识

作者: dodonaomikiki 时间: 2022-12-13 19:12

王守恩发表于 2022-12-11 07:52
直接在大数不容易算，间接在小数容易算，目的很明确：要在小数里找出规律来。

做一道题，我们要有收获 ...

王守恩
应该是我谢谢你！
针对原题，我还在思考！

个人觉得，2000多次，还是太多啦

作者: dodonaomikiki 时间: 2022-12-13 19:17
本帖最后由 dodonaomikiki 于 2022-12-13 19:26 编辑

\(    NEW \qquad PROBLEM：                   \)
现在有10个数字，最简单的十个数字：
\(    1  ,2 , 3 ,  4,  5    \qquad    6  ,7 ,8 , 9,  10          \)
现在对他们进行排序，变成：
\(    2, 4 , 6 , 8 , 10 \qquad    \qquad 9, 7,    5,    3 , 1          \)

一个大操作可以包含任意多次小操作！
小操作的意思：相邻两个数字进行互换！
限制条件：在一次大操作中，前面的奇数不可排到【新奇数】后面

比如：

在第一次大类操作中，56进行互换，
那么，前面的1，3不可以排到【新奇数5】

后面

问：
最少需要几次大类操作？

作者: dodonaomikiki 时间: 2022-12-13 19:47
针对\(15\)楼提出的问题：
进行了大致操作，不一定对！搞了八次大类操作，完成!\(FINISH\)

欢迎光临数学中国 (http://www.mathchina.com/bbs/)