Friend Number之打表

Friend Number之打表

问题描述: Paula和Tai是夫妻,他们的电话号码是 2200284 , Tai 告诉 Paula ,220与284是一对”Friend Number”,因为220的所有因子之和恰是284,而284的所有因子之和也恰是220,在小于1000的数字中,只有这一对数字是Friend Number。本题给出区间[a,b],计算在这个区间内有多少对Friend Number.

题目链接: https://vjudge.net/problem/NBUT-1223

对于求一个数字的所有因数,只能靠枚举,此题可以在外边先写程序计算出所有小于MAXN的friend number数对,然后此题的程序直接读取常量数组即可。为了把握求所有friend number的计算进度,这里编写一个C#的winForm窗体来观察。

计算的核心步骤为:

private int allFactorSum(int x)
{
    int s = 1;
    for(int i=2;i*i<=x;i++)
    {
        if (x % i == 0)
            s += i + x/i;
    }
    return s;
}

主调函数:

for (int i=0;i<MAXN;i++)
{
    int R = allFactorSum(i);
    if( i==allFactorSum(R) && i!=R && i<R)
    {
        Console.WriteLine("{0},{1}",i,R);
    }
}

但是像这种计算耗时非常长的操作,如果直接是加载窗体时触发,或者通过点击按钮触发,那么界面会卡住,直到计算完成后才恢复,因为计算时窗体的主线程被计算占用,无法响应其它的动作。所以要将主调函数的运算放在新的Task中去运行,将计算线程和界面线程分开。

为了看到计算进度,在窗体上添加一个progressBar。为了看到计算结果,添加一个ListBox,每当计算出一个结果,就将结果添加到ListBox中。另外,ListBox中的数据不易编辑,在计算之后使Button能够将数据导出为文本文件。

首先,将主调函数放在 Form_Load方法中,使用new Task().Start();的方式启动,这样窗体能够正常启动,计算过程也在进行。但如果在此时直接修改控件的属性,则会报“不是从创建控件的线程访问”,这个问题在 https://www.malic.xyz/archives/1957 中讨论过,只需要使用delegate指定函数,并使用Invoke将参数传到delegate中,就可以在Task中访问控件。delegate的new要在Form的构造函数中声明,如果在Form构造函数之外直接以初始化的形式,那就要求这个函数必须是static,而static类型要访问控件就又要将控件声明成static。所以为了直接使用控件,不需要将函数声明成static,而是选择在Form构造函数中声明相应的函数委托。

delegate void changeProgress(int x);
delegate void addItemToLb(string s);
delegate void setButtonEnabled(bool f);

changeProgress changeProgress1;
addItemToLb addItemTolb1;
setButtonEnabled setButtonEnabled1;

public Form1()
{
    InitializeComponent();
    changeProgress1 = new changeProgress(changeProgressFunction);
    addItemTolb1 = new addItemToLb(addItemToLbFunction);
    setButtonEnabled1 = new setButtonEnabled(setButtonEnabledFunction);
}

private void setButtonEnabledFunction(bool f)
{
    button1.Enabled = f;
}

private void addItemToLbFunction(string s)
{
    listBox1.Items.Add(s);
}

private void changeProgressFunction(int x)
{
    var t = (int)((1 + x) * 100.0 / MAXN);
    if (t > progressBar1.Value)
    {
        progressBar1.Value = t;
    }
}

Form_Load的方法写作:

private void Form1_Load(object sender, EventArgs e)
{

    new Task(() =>
    {
        Invoke(setButtonEnabled1, false);
        for (int i=0;i<MAXN;i++)
        {
            int R = allFactorSum(i);
            if( i==allFactorSum(R) && i!=R && i<R)
            {
                Invoke(addItemTolb1,String.Format("{0},{1}", i, R));
            }
            Invoke(changeProgress1, i);
        }
        Invoke(setButtonEnabled1, true);
        MessageBox.Show("FINISHED.","HINT",MessageBoxButtons.OK,MessageBoxIcon.Information);
    }).Start();
}

在计算结束之后,使用MessageBox弹出一个提示窗口表示计算已经完成。

最后再为按钮编写一个click事件,将计算结果输出成文本文件。需要计算完成后再导出,所以设定当计算完成后button的Enable才修改为true。

private void button1_Click(object sender, EventArgs e)
{
    System.IO.FileStream fp = new System.IO.FileStream("res", System.IO.FileMode.OpenOrCreate);
    System.IO.StreamWriter streamWriter = new System.IO.StreamWriter(fp);
    foreach (var it in listBox1.Items)
    {
        streamWriter.WriteLine(it);
    }
    streamWriter.Close();
    fp.Close();
    Invoke(setButtonEnabled1, false);
}

这样大概几分钟就将结果全部算出,最后编写C++程序,把已经获得的Friend number当作常量数组编写到代码当中:

#include <cstdio>
#include <cstring>

const int tA[] = {
220,1184,2620,5020,6232,10744,12285,17296,63020,66928,
67095,69615,79750,100485,122265,122368,141664,142310,171856,176272,185368,196724,
280540,308620,319550,356408,437456,469028,503056,522405,600392,
609928,624184,635624,643336,667964,726104,802725,879712,898216,947835,998104,
1077890,1154450,1156870,1175265,1185376,1280565,1328470,1358595,
1392368,1466150,1468324,1511930,1669910,1798875,2082464,2236570,2652728,2723792,
2728726,2739704,2802416,2803580,3276856,3606850,3786904,3805264,
4238984,4246130,4259750,4482765,4532710,4604776};


const int tB[] = {
284,1210,2924,5564,6368,10856,14595,18416,76084,66992,
71145,87633,88730,124155,139815,123152,153176,168730,176336,180848,203432,202444,
365084,389924,430402,399592,455344,486178,514736,525915,669688,
686072,691256,712216,652664,783556,796696,863835,901424,980984,1125765,1043096,
1099390,1189150,1292570,1438983,1286744,1340235,1483850,
1486845,1464592,1747930,1749212,1598470,2062570,1870245,2090656,2429030,2941672,2874064,
3077354,2928136,2947216,3716164,3721544,3892670,4300136,
4006736,4314616,4488910,4445050,5120595,6135962,5162744};

const int MAXN = 1000000;

void solve(int a,int b)
{
	int i,N=sizeof(tA)/sizeof(int);
	int s=0;
	for(i=0;i<N;i++)
	{
		if(tA[i]>=a && tB[i]<=b)
		{
			s+=1;
		}
	}
	printf("%d\n",s);
}

int main(void)
{

	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		solve(a,b);
	}
	


	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注