算法题:UVA 138

Street Numbers

A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it.

Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):

        6         8
       35        49

Input and Output

There is no input for this program. Output will consist of 10 lines each containing a pair of numbers, each printed right justified in a field of width 10 (as shown above).

题意: 简单来说, 求出10组k,n, 满足 1 + 2 +... + k = k + 1 + k + 2 + ... + n;

思路: pell方程的应用,利用前一个解求下一个解求出10组即可。

代码:

#include <stdio.h>
#include <string.h>

int x, y, x0, y0, t, n;
int main() {
    x = x0 = 3; y = y0 = 2; n = 2;
    for (int i = 0; i < 10; i ++) {
    t = x * x0 + n * y * y0;
    y = x * y0 + y * x0;
    printf("%10d%10d\n", y / 2, (t - 1) / 2);
    x = t;
    }
    return 0;
}

查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索this
, number
, and
The
139、138美容人才网、ip138、138是联通还是移动、138战歌网,以便于您获取更多的相关知识。

时间: 2025-01-19 18:36:54

算法题:UVA 138的相关文章

算法题之UVA 763

Fibinary Numbers The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence ``1010'' is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence

算法题:uva 10318

题目链接: 首先,可以确定每个格子只能选一次,因为选任何大于0的偶数次,等于没有效果 一样. 然后,就可以把这题理解成从r*c的矩阵中选择一些格子进行"点亮"操作,使得最终所 有格子都是"亮"的状态.那么,每个格子要么有点亮操作,要么没有,总共复杂度为2^25,显然必须 进行减枝. 假设从第一行第一列开始,从左往右,从上往下一次依次选择,对于当前所在位置( x, y),它已经不能影响到x-2以前的行数了,所以当到x行时,如果第x-2行没有全部点亮,则进行减枝 . 此

算法题:uva 1330

题目链接: http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076 以前做过一道一维的,这题只是变成了二维的,其他方法都一样.HDU 1506  Largest Rectangle in a Histogram   题解 代码1: #include<cstdio> #include<cs

经典算法题每日演练——第六题 协同推荐SlopeOne 算法

原文:经典算法题每日演练--第六题 协同推荐SlopeOne 算法               相信大家对如下的Category都很熟悉,很多网站都有类似如下的功能,"商品推荐","猜你喜欢",在实体店中我们有导购来为我们服务,在网络上 我们需要同样的一种替代物,如果简简单单的在数据库里面去捞,去比较,几乎是完成不了的,这时我们就需要一种协同推荐算法,来高效的推荐浏览者喜 欢的商品. 一:概念      SlopeOne的思想很简单,就是用均值化的思想来掩盖个体的打

经典算法题每日演练——第八题 AC自动机

原文:经典算法题每日演练--第八题 AC自动机        上一篇我们说了单模式匹配算法KMP,现在我们有需求了,我要检查一篇文章中是否有某些敏感词,这其实就是多模式匹配的问题. 当然你也可以用KMP算法求出,那么它的时间复杂度为O(c*(m+n)),c:为模式串的个数.m:为模式串的长度,n:为正文的长度,那 么这个复杂度就不再是线性了,我们学算法就是希望能把要解决的问题优化到极致,这不,AC自动机就派上用场了.    其实AC自动机就是Trie树的一个活用,活用点就是灌输了kmp的思想,从

经典算法题每日演练——第二十五题 块状链表

原文:经典算法题每日演练--第二十五题 块状链表 在数据结构的世界里,我们会认识各种各样的数据结构,每一种数据结构都能解决相应领域的问题,每一种数据结构都像 是降龙十八掌中的某一掌,掌掌毙命... 当然每个数据结构,有他的优点,必然就有它的缺点,那么如何创造一种数据结构 来将某两种数据结构进行扬长避短,那就非常完美了.这样的数据结构也有很多,比如:双端队列,还有就是今天讲的 块状链表,    我们都知道 数组 具有 O(1)的查询时间,O(N)的删除,O(N)的插入...            

一个算法题,求答案啊啊啊啊

问题描述 一个算法题,求答案啊啊啊啊 白班 09:00-18:00 通班 09:00-21:00 每个人每个月通班数量必须等于早中班和中晚班数量之和 早中班 09:00-15:00 中晚班 15:00-21:00 假设:每月按照30计算. 排班规则: 1.每个人每个月固定休息6天连续上班天数不超过7天. 2.每天各班次上班的人数最低需求:8个白班5个通班1个早中班,2个中晚班. 3.每个月每个人的通班天数安排不超过8天. 4.每个人每个月早中班和中晚班的天数之和需要与通班天数相等. 5.每月最多

算法题:把阿拉伯金额转化为汉字表示的金额

n年没写算法题了,今天用了20分钟写了一个,要求如题,感觉算法有所退步,老了 using System; using System.Text; namespace money { class Program { static void Main(string[] args) { StringBuilder sb=new StringBuilder(); var strValue = Console.ReadLine(); var strlist = strValue.Split('.'); if

算法题:poj 2541 Binary Witch(KMP水过,逆序转换)

链接: http://poj.org/problem?id=2541 分析与总结: 做这题估算了下复杂度,觉得无论KMP再怎么快,这题暴力也肯定要超时的. 想了很久也没想出个好办法,于是决定暴力之,但是TLE了....于是就放了几天.之后看了下discuss ,这题的正解应该是状态压缩dp,不过目前我还不懂,跪了. 之后百度发现也可以用KMP水过,虽然是因为数据水才过的,不过这种思路很巧妙,值得借鉴! 直接暴力是枚举字符串的后面13个的字母,然后再用KMP匹配,这样的话,就绪要枚举多次,分别是

算法题:HDU 2594 Simpsons’ Hidden Talents(KMP)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=2594 题目大意: 给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串. 分析与总结: 真正理解好KMP算法,这题就是水题. 首先求出s1的失配函数,然后在s2中 寻找s1字符串. 在寻找字符串过程中,会有一个状态值j,这个值表示的是当前在s2中已经匹配 了多少个s1的字符. 所以,全部匹配完后,最后j的值就是以s2的最后一个字符结尾,和s1的前缀相匹 配的最长字符串.也就是所求的