魔方吧·中文魔方俱乐部

标题: 有趣的数论问题 [打印本页]

作者: qiaoyisi 时间: 2013-12-29 23:42:31 标题: 有趣的数论问题

附件: 1111.jpg (2013-12-29 23:42:25, 17.4 KB) / 下载次数 111
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjMwNjY1fGE0MTU2M2ZmfDE3NjEzNDExNDN8MHww

作者: tm__xk 时间: 2013-12-30 00:14:44

13824.
字数.

作者: bristlegrass 时间: 2013-12-30 11:17:22

同楼上 13824

作者: qiaoyisi 时间: 2013-12-30 13:13:46

给一下具体过程，谢谢！

作者: tm__xk 时间: 2013-12-30 20:51:13

本来我是直接跑程序秒的.既然要过程..那就随便码个好了..
157随意,造成4个空当.
穷举2468在其中的分布.
I.13
"3"需3和9分隔,故6为"1".方案数为(12*6*2=)144.
II.112
同理6为"1",方案数为(12*12*2*5=)1440.
III.1111
方案数为(24*30=)720.
综上,总方案数为(6*(144+1440+720)=)13824.

作者: tm__xk 时间: 2013-12-30 21:53:26

我一定是太无聊了..竟然无聊到用容斥原理算这个问题..
为方便观看,用图来表示是否能相邻的关系..
用点表示数,用边表示不能相邻的关系..可以看到..其实就是2468构成K4,369构成K3(二者公用6)(当然还有157孤立).
我们来看看取其中若干条边后,使这些边两端相邻的方案数..
应该看到,取出的若干条边,如果存在圈,或者存在度数>=3的点,就很没有考虑的意义了..
还有,这里总共6个点,没有圈,于是至多取5条边.
下面记A[i]为取i条边时对应的方案数.
################以上是废话.以下是无聊.以下纯目测,所以嫌太简单的别找我要过程.(ls的过程也是目测,同样别找我解释.)
I.A[0]=9!
II.A[1]=8!*2*9
III.A[2]=7!*(2*21+2^2*15)
IV.A[3]=6!*(2*30+2^2*33+2^3*3)
V.A[4]=5!*(2*24+2^2*27)
VI.A[5]=4!*2*12
综上,总方案数为A[0]-A[1]+A[2]-A[3]+A[4]-A[5]=9!-8!*2*9+7!*(2*21+2^2*15)-6!*(2*30+2^2*33+2^3*3)+5!*(2*24+2^2*27)-4!*2*12=13824.

作者: superacid 时间: 2013-12-30 22:32:28

我是来吐槽楼主懒得打字的

作者: bristlegrass 时间: 2013-12-31 09:15:08

本帖最后由 bristlegrass 于 2013-12-31 10:58 编辑

好吧...我也是跑程序的...
要思路的话就随便写一个吧

把数分成4组:
a.157
b.248
c.39
d.6

6在中间:
d和bc都不能相邻,所以先从a组抽2个数组成一个集合(e):3*2=6;
a组剩下一个数(f);
b组排列数:3*2=6;
把c组插入b组,分情况:
A.同在一端,无符合题意的排列:0;
B.各在一端,则ef只能插在248中间:2*2=4;
C.一个在一端一个在中间,则ef还有一个要插中间:2*2*2*(7-1)*2=96;
D.在同一空当,则ef有两个空当必插:2*2*2=8;
E.在不同空当:2*6*7=84;
综上:6*6*(0+4+96+8+84)=6912.

6在两端(2):
d和bc都不能相邻,所以先从a组抽1个数组成一个集合(g):3;
a组剩下两个数(h);
b组排列数:3*2=6;
把c组插入b组,分情况:
F.同在一端,无符合题意的排列:0;
G.各在一端,则h只能插在b中间:2*2=4;
H.一个在一端一个在中间,则h还有一个要插中间:2*2*2*(7-1)*2=96;
I.在同一空当,则h有两个空当必插:2*2*2=8;
J.在不同空当:2*6*7=84;
综上:2*3*6*(0+4+96+8+84)=6912.

总:6912+6912=13824.

也不知道对不对-.- 顺便说一下我的程序跑了72秒是不是很渣...
ps:改了一下算法,现在36秒...

作者: tm__xk 时间: 2013-12-31 14:56:44

bristlegrass 发表于 2013-12-31 09:15
好吧...我也是跑程序的...
要思路的话就随便写一个吧

呃..我的程序..大概跑了..半秒?→_→

作者: tm__xk 时间: 2013-12-31 14:58:35

话说..一般地讲..这就是求图的哈密顿路的数量吖..

作者: bristlegrass 时间: 2013-12-31 18:15:05

本帖最后由 bristlegrass 于 2013-12-31 18:21 编辑

tm__xk 发表于 2013-12-31 14:56
呃..我的程序..大概跑了..半秒?→_→

QAQ,好吧我承认我很渣,我是穷举出来的-.-

作者: tm__xk 时间: 2014-1-1 00:11:54

bristlegrass 发表于 2013-12-31 18:15
QAQ,好吧我承认我很渣,我是穷举出来的-.-

嘛..我也是穷举吖..这也就是穷举了吧..
嘛..怎么说也每层都把限制条件弄进去了..怎么说也写了个九重循环..跑太慢也不好意思←_←

作者: qiaoyisi 时间: 2014-1-1 14:44:19

嗯，谢谢，1~10，有算术方法吗？好像是20000多一点把

作者: tm__xk 时间: 2014-1-1 21:31:02

qiaoyisi 发表于 2014-1-1 14:44
嗯，谢谢，1~10，有算术方法吗？好像是20000多一点把

请定义所谓的"算术方法".

ps.答案是22032.

作者: bristlegrass 时间: 2014-1-3 10:30:18

tm__xk 发表于 2014-1-1 00:11
嘛..我也是穷举吖..这也就是穷举了吧..
嘛..怎么说也每层都把限制条件弄进去了..怎么说也写了个九重循环 ...

刚刚发现写成九重循环确实比穷举九位数快......不到0.02s

作者: tm__xk 时间: 2014-1-3 17:00:34

bristlegrass 发表于 2014-1-3 10:30
刚刚发现写成九重循环确实比穷举九位数快......不到0.02s

必须的吖....

作者: qiaoyisi 时间: 2014-1-3 23:38:52

tm-xk能发个计算程序我邮箱吗？248705037@qq.com,我怎么计算1~12要用130多个小时，可能是算法有问题。

附件: 123.jpg (2014-1-3 23:38:45, 15.9 KB) / 下载次数 50
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjMwOTQ3fDZlYjIzZjE3fDE3NjEzNDExNDN8MHww

作者: tm__xk 时间: 2014-1-4 00:33:10

qiaoyisi 发表于 2014-1-3 23:38
tm-xk能发个计算程序我邮箱吗？,我怎么计算1~12要用130多个小时，可能是算法有问题。

1到10的22032种..直接十重循环..每次都分别验证那一位..很快的吖..
算法很简单就不发了吧..(其实是因为我没有用正规的编程语言..不方便别人用..)

你说的130多个小时的是1到12?我没说我算过1到12的吖..不知道会不会很慢..
呃..如果你是想说1到10..笔误了的话..那130多个小时就太慢了..不至于是穷举10!种再验证吧..
等我看看同样方法开到12重能不能跑得动←_←

嘛..其实一般地..这就是个哈密顿路计数..没啥好再取巧的了吧..

作者: qiaoyisi 时间: 2014-1-4 15:47:17

我算1~11不过几秒，1~12就是12!=479001600 算1秒能处理1000个排列，也要479001.6秒，即7983.36分钟，133.056小时，需要我可以把我程序给你

作者: tm__xk 时间: 2014-1-4 23:36:02

qiaoyisi 发表于 2014-1-4 15:47
我算1~11不过几秒，1~12就是12!=479001600 算1秒能处理1000个排列，也要479001.6秒，即7983.36分钟，133.05 ...

1到12的..结果是476928么..
十二重循环..跑了48s..
需要的话我可以把程序贴上来..
(不过我觉得就是简单的循环而已..实在没啥贴的必要..)
(算法就相当于几个好多层循环好多个if而已..而我不是用正规的编程语言写的..所以格式相对比较不一样..这才是我不想贴上来的原因..)

作者: qiaoyisi 时间: 2014-1-6 12:42:39

谢谢把程序发上来看看。

作者: tm__xk 时间: 2014-1-6 13:37:19

qiaoyisi 发表于 2014-1-6 12:42
谢谢把程序发上来看看。

实在没啥值得一提的..

附件: [1到12的程序] 1..12.png (2014-1-6 13:36:43, 25.88 KB) / 下载次数 68
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjMxMTE1fDBkOTdiNjJmfDE3NjEzNDExNDN8MHww

作者: qiaoyisi 时间: 2014-1-6 14:31:17

好的，谢谢！

作者: tm__xk 时间: 2014-1-6 14:35:17

qiaoyisi 发表于 2014-1-6 14:31
好的，谢谢！

你的程序不是大概这样的么..

作者: qiaoyisi 时间: 2014-1-6 15:03:28

我给你发消息留言了

作者: qiaoyisi 时间: 2014-1-16 12:01:47

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace Pai
{
public partial class FormSort : Form
{
      List<List<int>> lli = new List<List<int>>();
      public FormSort()
      {
         InitializeComponent();
      }

      private void FormSort_Load(object sender, EventArgs e)
      {
         lbMsg.Text = "";
         tCount.Enabled = false;
         bResult.Enabled = false;
      }

      private void bCalculate_Click(object sender, EventArgs e)
      {
         lli.Clear();

         lbMsg.Text = "";
         tResult.Clear();
         bResult.Enabled = false;
         tCount.Enabled = false;

         List<int> d = new List<int>();
         int len;
         int i = 0;

         try
         {
            if (string.IsNullOrEmpty(tNum.Text))
            {
                  MessageBox.Show("请输入数组。");
                  return;
            }

            string[] arrStr = tNum.Text.Split(',');
            foreach (string str in arrStr)
            {
                  int num = Convert.ToInt32(str);

                  if (d.Count == 0)
                     d.Add(num);
                  else
                  {
                     if (num < d[0])
                        d.Insert(0, num);
                     else if (num > d[d.Count - 1])
                        d.Add(num);
                     else
                     {
                        for (i = 0; i < d.Count - 1; i++)
                        {
                              if (num > d[i] && num < d[i + 1])
                              {
                                 d.Insert(i + 1, num);
                                 break;
                              }
                        }
                     }
                  }
            }
            len = d.Count;
         }
         catch (Exception ex)
         {
            MessageBox.Show(ex.Message);
            return;
         }

         List<int> tmp = new List<int>();
         List<int> t = new List<int>();

         for (i = 0; i < len; i++)
         {
            tmp.Add(0);
            t.Add(d[i]);
         }

         int strCount = 0;
         while (t.Count == d.Count)
         {
            bool bFound = false;

            if (t.Count > 1)
            {
                  for (i = 0; i < t.Count - 1; i++)
                  {
                     if (t[i] == 0 && Math.Abs(t[i + 1]) > 1 || t[i + 1] == 0 && Math.Abs(t[i]) > 1)
                     {
                        bFound = true;
                        break;
                     }
                     else if (t[i] - t[i + 1] < -1 || t[i] - t[i + 1] > 1)
                     {
                        if (gcd(t[i], t[i + 1]) > 1)
                        {
                              bFound = true;
                              break;
                        }
                     }
                  }
            }

            if (!bFound)
            {
                  //lli.Add(t);
                  strCount++;

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)