帮忙写个算法：两个递增数列排序后求第n个数

止戈而立 2009-02-20 01:22:42

加精

...全文

2900 62 打赏收藏转发到动态举报

写回复

用AI写文章

62 条回复

切换为时间正序

请发表友善的回复…

发表回复

bbjiabcd 2012-08-09

打赏
举报

也就是算法问题。虽然已经结帖，我再发个不用数组的C# WinForm 的
两数列放大 (A+B)(A-B)



        private void btCalc_Click(object sender, EventArgs e)

        {

            int a = Convert.ToInt32(txtA.Text);

            int b = Convert.ToInt32(txtB.Text);

            int n = Convert.ToInt32(txtn.Text);

            int c1 = a - b;

            int c2 = a + b;

            int i;

            int d1 = 1;

            int d2 = 1;

            int f1=c1;

            int f2=c2;

            int r=c1;

            txtPaixu.Text = c1.ToString();

            if (n > 1)

            {

                for (i = 2; i <= n; i++)

                {

                    if (f1 == f2)

                    {

                        d1 += 2;

                        d2 += 2;

                        f1 = c1 * d1;

                        f2 = c2 * d2;

                        r = f1;

                    }

                    else if (f1 < f2)

                    {

                        d1 += 2;

                        r = f2;

                        f1 = c1 * d1;

                    }

                    else

                    {

                        d2 += 2;

                        r = f1;

                        f2 = c2 * d2;

                    }

                    txtPaixu.Text += "," + r.ToString();

                }

            }

            txtAns.Text = r.ToString();

        }

躺枪同学 2012-06-25

打赏
举报

高手，真厉害，直接把代码都给出来了。

guang090809080908 2011-08-07

打赏
举报

学习一下

japanbbq666 2011-07-11

打赏
举报

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/*已知数A和数B，且A>B
数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)……
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)……
两个数列放到一起排序，求排序后的第n个数是多少？
*/

namespace 两个数列重排序输出第n个数值
{
class Program
{
static void Main(string[] args)
{
System.Console.WriteLine("input number A:");

int a = int.Parse(System.Console.ReadLine());

System.Console.WriteLine("input number B:");

int b = int.Parse(System.Console.ReadLine());

double[] arr1 = new double[20];

for (int i = 0; i < arr1.Count(); i++)
{
arr1[i] = 1 / ((double)a + (double)b) + i * 2 / ((double)a + (double)b);
}

double[] arr2 = new double[20];

for (int i = 0; i < arr2.Count(); i++)
{
arr2[i] = 1 / ((double)a - (double)b) + i * 2 / ((double)a - (double)b);
}

double[] arrAll = new double[20];

for (int i = 0; i < arrAll.Count(); i++)
{
if (i < 10)
{
arrAll[i] = arr1[i];
}

else
arrAll[i] = arr2[i];

}

Array.Sort(arrAll);

System.Console.WriteLine("重排列后数组如下");

for (int i = 0; i < arrAll.Count(); i++)
{
System.Console.Write(arrAll[i] + " ");
}

System.Console.WriteLine("请输入要的第n个数");

int index = int.Parse(System.Console.ReadLine());

System.Console.WriteLine(arrAll[index - 1]);

}
}
}

新手，多多指教！

sanae 2011-05-01

打赏
举报

俺是新人，不过还是有个想法求指正：

可以只保存n<=lcm(A+B, A-B)的结果，其中lcm为最小公倍数
当n>lcm(A+B, A-B)时
可以由n % lcm(A+B, A-B)的结果加上某个常数在O(1)时间内算出来

sknice 2009-07-24

打赏
举报

帮忙看看我的问题
http://topic.csdn.net/u/20090724/17/90f076b3-8948-4cea-83e3-78dc96146103.html?seed=1804070590&r=58604121#r_58604121

--小F-- 2009-04-14

打赏
举报

牛人实在是太多了

wonderfuljoy 2009-03-25

打赏
举报

学习学习，顶下！

suiyili 2009-02-26

打赏
举报

把两列数组都乘以(a-b), 那么一列就变成是1,3,5...（我们称它为A），另一列就是1*(a-b)/(a+b), 3*(a-b)/(a+b),...(B)，合并后的数组为C
我们知道给定n, B(n) 的给定一定比 A(n) 要小，但是 C(n) 至少比 B(n) 大。C(n) <= B(n) < A(n)
我们要求C(n), 但是我们很容易找到B(n)=(2n-1)*(a-b)/(a+b),(n = 1, 2, 3..)。
然后，我们知道A里面都是整数(1,3,5,7,..)，那么，我们通过对B(n)取整数，看距离这个整数最近的奇数是几，就知道B(n)后面包含了多少A的元素。
至于A,B重复的元素，只要看看能够使得k*(a-b)/(a+b)为整数的最小k是几，然后任何k的倍数都是了。

delphi_tang 2009-02-26

打赏
举报

大家看看我的，楼主也看过来。。。





#include <iostream.h>



#define A 3

#define B 1



float an(int n)

{

    return (2*n-1.0) / (A+B);

}



float bn(int n)

{

    return (2*n-1.0) / (A-B);

}



float cn(int n)

{

    int x = 0;

    int y = 0;



    while( (x+y) < n )

    {

        y++;



        int tmp = (A+B)*y - B;



        if( (tmp%(A-B)) == 0 )

        {

            x = tmp / (A-B);

        }

        else

        {

            x = tmp/(A-B) + 1;

        }



        x--;

    }



    if( (x+y) == n )

    {

        return bn(y);

    }

    else

    {

        y--;



        return an(n-y);

    }

}



void main()

{

    cout<<"an:"<<endl;

    for(int i=1; i<=20; i++)

    {

        cout<<an(i)<<" ";

    }

    cout<<endl;



    cout<<"bn:"<<endl;

    for(int i=1; i<=20; i++)

    {

        cout<<bn(i)<<" ";

    }

    cout<<endl;



    cout<<"cn:"<<endl;

    for(int i=1; i<=20; i++)

    {

        cout<<cn(i)<<" ";

    }

    cout<<endl;



}

knate 2009-02-26

打赏
举报

已知数A和数B，且A>B
数列一：第一个数为1/(A+B)，增量为2/(A+B)，往下递增，即1/(A+B)、3/(A+B)、5/(A+B)……
数列二：第一个数为1/(A-B)，增量为2/(A-B)，往下递增，即1/(A-B)、3/(A-B)、5/(A-B)……
两个数列放到一起排序，求排序后的第n个数是多少？

两数列放大 (A+B)(A-B)
数列1 为an = (2n+1)(A-B) n= 0,1,2,3.....
数列2 为bn = (2n+1)(A+B) n= 0,1,2,3...

前提A != B
设ai = bk;
(2i+1)(A-B) = (2k+1)(A+B)
2(i-k)A = 2(i+k+1)B (*)

假设第n个数为an

an 的ai在合并数列的下标为 [i + k+1](取整)
设第n个数为ai
即
i+k+1 = n-1 (1)

i-k = (n-1)B/A (2)
(1)和(2) 联合得
i = F(n) (3)
//修正: 如果(*) 关于i,k 有整数解时,且bn优先排序在an时修正为F(n)+1,其他情况不变

同样
设第n个数为bk
bk 的在合并数列的位置为 [k + i+1](取整)
k+i+1 = n-1
i-k = (n-1)B/A

k = G(n) (4)
//修正: 如果(*) 关于i,k 有整数解时,且an优先排序在bn时修正为G(n)+1,其他情况不变

程序应该在常数时间内结束

zte_boy 2009-02-25

打赏
举报

顶一下

zte_boy 2009-02-25

打赏
举报

顶一下

ldyqz2003 2009-02-25

打赏
举报

UP一下

owenliangbin 2009-02-25

打赏
举报

long n_value=n*(A-B);
for(int i=1;i<=n;i++)
{

if(i*(A+B)>n_value)return n_value/(A-B)/(A+B);
if(i*(A+B)>n_value-2*(A-B))return i/(A-B);
n_value-=2*(A-B);
}

qzl123666 2009-02-24

打赏
举报

支持2楼，2楼想法很不错

dqceo 2009-02-24

打赏
举报

[Quote=引用 17 楼 min_jie 的回复:]
引用 13 楼 much0726 的回复:
不知道是不是这个意思,止戈老大看看:

C# code
decimal A = 4;
decimal B = 1;

int IndexA = 1;
int IndexB = 1;

ArrayList arry = new ArrayList();

int FindIndex = 3;
int n = 0;

while (n < FindIndex)
…
[/Quote]

good!